0

I have to create a function respecting an O(n) complexity and to do that i want to use the str() function.

Can someone explain me if :

str(1000)

Is this code O(1) or O(4) because of the 1+0+0+0 ?

OneCricketeer
  • 179,855
  • 19
  • 132
  • 245
Freddy
  • 47
  • 9
  • 2
    How are you planning to use it? I would expect it to be O(n) to the size of the input string, but the function you are writing may be O(n) on something else. – General Grievance Mar 30 '22 at 14:09
  • 5
    O(4) _is_ O(1). If the length of your number is variable, then it's O(n) on that length. But unless your numbers are of unlimited size, that length is bounded, so it's O(1). – khelwood Mar 30 '22 at 14:11
  • The number could be 2 or 1234567... and I just want to know if str(2) and str(1234567) have the exact same complexity or if it depends on the number of digits – Freddy Mar 30 '22 at 14:23
  • They do have the same complexity. And it does depend on the number of digits – OneCricketeer Mar 30 '22 at 14:25
  • @OneCricketeer I have absolutely no idea how the function might works then.... How these two examples can have the same complexity if the complexity depends on the number of digits ? – Freddy Mar 30 '22 at 14:28
  • 2
    @Freddy Time complexity is a way of describing how the time taken changes with different inputs. It's not one complexity for one input and one complexity for another input. – khelwood Mar 30 '22 at 14:29
  • 1
    Because both of them run the same function. It's roughly linear runtime at the byte level. A function shouldn't change its runtime complexity based on its input. – OneCricketeer Mar 30 '22 at 14:29
  • Many thanks guys, do I have to understand that this function has a constant complexity then ? Like it will be O(1) with any input ? – Freddy Mar 30 '22 at 14:33
  • 1
    No, it's O(n), where `n` is the logarithm of the magnitude of the value. (Because logarithms of different bases are the same to within a constant factor.) Basically, `str` is a base conversion from base `B` (where `B` is determined by how Python represents `int` values) to base 10. – chepner Mar 30 '22 at 14:35
  • [Convert string to number & vice versa complexity](https://stackoverflow.com/q/4483189/3890632) – khelwood Mar 30 '22 at 14:37

3 Answers3

4

As can be seen from the source code, the implementation of int.__str__ has runtime complexity of O(m*n) where m is the number of binary digits and n is the number of decimal digits. Since for an integer i the number of digits in an arbitrary base b is given by log(i, base=b) and logarithms in different bases differ only by a constant, the runtime complexity is O(log(i)**2), i.e. quadratic in the number of digits.

This can be verified by running a performance test:

import perfplot

perfplot.show(
    setup=lambda n: 10**n,
    kernels=[str],
    n_range=range(1, 1001, 10),
    xlabel='number of digits',
)

performance plot

The quadratic time complexity in the number of digits is also mentioned in the issue for CVE-2020-10735:

[...] A huge integer will always consume a near-quadratic amount of CPU time in conversion to or from a base 10 (decimal) string with a large number of digits. No efficient algorithm exists to do otherwise.

a_guest
  • 34,165
  • 12
  • 64
  • 118
2

O(n) in the context of a data structure just means if there are n items then an operation on that structure will require (in the order of) n iterations or passes to achieve the desired result. If you're constructing a string from an integer, then I guess the complexity would be O(log10(n))

EDIT: from the Python docs:

If neither encoding nor errors is given, str(object) returns object.str(), which is the “informal” or nicely printable string representation of object.

Python detects that the object is an int, therefore it will create a string from that int. One way of implementing this conversion is:

if n == 0:
    return "0"
negative = n < 0
if negative:
    n = -n
out = ""
while n > 0:
    digit = n % 10
    n /= 10
    out = chr(48 + digit) + out
if negative:
    out = "-" + out

The number of iterations inside that while loop depends on the number of digits in decimal that n contains, which is log10(n).

Jack Bendtsen
  • 104
  • 1
  • 5
  • Where are you getting log from? There are n digits in the integer to build a string buffer from – OneCricketeer Mar 30 '22 at 14:14
  • 2
    It’s from `n` being an integer who’s sting length grow logarithmically compared to the number `n`. Just a different way of defining `n`. – Mark Mar 30 '22 at 14:15
  • 1
    @Mark If I give a list of 4 integers to find the max of them, that's no different runtime if I give 10 or 1000. Why are we treating digits of a number that build a string, any different? The base of the number shouldn't matter. N is the number of digits, not the number itself – OneCricketeer Mar 30 '22 at 14:18
  • @OneCricketeer How would you write a function to construct a string from an integer, without using any other functions? – Jack Bendtsen Mar 30 '22 at 14:20
  • The input length is, roughly, the number of bits needed to represent the integer. Loosely speaking, the complexity is O(n), because the number of bits is within a constant factor of the number of decimal digits. – chepner Mar 30 '22 at 14:21
  • @Jack it's not about other functions, I'm saying specifically for the str function. You can use modulo and division to pull off digits, then join them to a string as an alternative answer, but the runtime should be the same – OneCricketeer Mar 30 '22 at 14:24
  • @OneCricketeer Correct. My point was that the complexity of the algorithm that does that is `O(log10(n))` – Jack Bendtsen Mar 30 '22 at 14:25
  • That is assuming N is a decimal number (the literal input) not the number of digits in the input, which is what I was referring to, sure, I understand now – OneCricketeer Mar 30 '22 at 14:27
  • _"then I guess the complexity"_. Any documentation to back this? – Abhinav Mathur Mar 30 '22 at 14:35
  • Note: using `str + str` in your example is no longer linear runtime - https://stackoverflow.com/questions/34008010/is-the-time-complexity-of-iterative-string-append-actually-on2-or-on – OneCricketeer Mar 30 '22 at 14:50
  • 1
    @OneCricketeer You are technically correct! However given that most integers are so small in isolation, big O only matters in an academic context, which is probably where OP was coming from when they asked this question. But yes, prepending an array does require moving all of the elements unless you already allocated space in front of the array beforehand, though I don't think this is the sort of thing people concern themselves with when writing in Python... – Jack Bendtsen Mar 30 '22 at 14:55
  • You code example uses an outer loop which is linear in the number of digits but what about `n % 10` and `n // 10`? These would have to be O(1) in the number of digits of `n` in order to yield an overall linear dependency. – a_guest Mar 30 '22 at 15:02
  • 3
    It turns out, the runtime complexity of `str(i)` for some integer `i` is `O(log(i)**2)`, please see [my answer](https://stackoverflow.com/a/71680813/3767239). It is correct that the number of *iterations* for `while n > 0` is proportional to `log(n)` but the complexity of operations inside that loop, `n % 10` and `n // 10`, also depends on the number of digits of `n`, hence the overall quadratic dependency. – a_guest Mar 30 '22 at 16:36
0

The function is used for string conversion. That means converting each of the value into a string. The complexity is depended on the length. If the the full length is n so the complexity will be O(n). If the size is a fixed number, in this case it will be executed a constant size. We represent the constant as O(1).

Promila Ghosh
  • 389
  • 4
  • 12