1
$\begingroup$

just given solution on this post

i had mention the time complexity to convert string to int is O(n), also verifying this post

now in one of comment fellow SO user, corrected me with example also mention in solution, that for every 10x increase in size time is increased by 100x time.

so i found, post where it mention the time complexity is O(n) is wrong, which is actually O(n*n).

so can anyone explain this, what is the time complexity of converison ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

It depends on whether the string representation is in base 10 or base 16.

Conversion to/from base 10

Normally, when an integer is represented as a string, it is represented in base 10. Then here is the running time:

It depends how you count. Theoretical analysis requires a model of the time it takes to do different operations, and depending on which model you choose, you get a different answer.

One way to count running time is to assume that each basic operation takes one unit of time, and that you can add, subtract, multiply or divide two integers (no matter how large) in one step. If you adopt this approach, then it is possible to do the conversion in $O(n)$ time.

Another way to count running time is to assume that each basic operation takes one unit of time, but each operation can only work on a fixed-size value: for instance, you can add or multiply two 32-bit integers in one step, but you cannot add/multiply arbitrary-size integers in one step (that might require many steps). If you adopt this method of counting, then the natural algorithms for conversion take $O(n^2)$ time.

The former approach to modelling runtime is typically more appropriate when working with small numbers (e.g., that fit into a single machine register). The second is often more appropriate when working with very large numbers.

Conversion to/from base 16

However, the main answer there proposes converting to base 16 (without really highlighting that is what it is doing). It turns out that converting to/from base 16 is much faster: it can be done in $O(n)$ time with a straightforward algorithm, regardless of how you count running time.

Improve this answer
$\endgroup$
6
  • $\begingroup$ It looks like this answer is somewhat misleading. The phenomenon here is that the usual conversion of an integer from base 2 to base 10 is $O(n^2)$ , but the conversion from base 2 to base 16 in $O(n)$. $\endgroup$
    – John L.
    Jul 17, 2022 at 4:38
  • $\begingroup$ @JohnL., oh, good point! I missed that part of the answer on Stack Overflow. Thank you for highlighting that. I've updated my answer accordingly. $\endgroup$
    – D.W. ♦
    Jul 17, 2022 at 7:33
  • $\begingroup$ can you explain why base 2 to base 10 it is taking 0(n*n) and for base 6 it is doing it in O(n)? $\endgroup$
    – sahasrara62
    Jul 17, 2022 at 8:30
  • $\begingroup$ I added integer division to the first approach in the answer since it appears in the usual algorithm. However, division is not strictly needed as the divisor here is the base, which can be assumed as a fixed number. Integer division by a fixed number can be replaced by additions and multiplications (and comparison to 0) without changing the $O(n)$ time-complexity of the conversion. $\endgroup$
    – John L.
    Jul 17, 2022 at 17:00
  • 1
    $\begingroup$ @JohnL. thanks it cleared the doubt also here is a little python implementation explaination $\endgroup$
    – sahasrara62
    Jul 17, 2022 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.