I cannot calculate the time complexity for this problem

Hi there,
I was watching a mock interview, and the candidate was asked to solve this problem, and he made the solution as shown in the picture:

He said time complexity would be O(log n), and the interviewer confirmed it.

I thought it is O(n), because the more digits in the integer, the more loops done by “while” loop, so the more the input size of this function, the more loops will be done.
integer of 3 digits, will take 3 loops
integer of 4 digits, will take 4 loops
and so on.

I don’t why I thought about it as number of digits, I feel something wrong in my way, but I don’t know how to think of increasing input when it is just a number not a size of something.

I think I should say it like this:
0 … 1 loop
5 … 1 loop
10 … 2 loops
50 … 2 loops
100 … 3 loops
500 … 3 loops
1000 … 4 loops
5000 … 4 loops
10000 … 5 loops
50000 … 5 loops
100000 … 6 loops
500000 … 6 loops
1000000 … 7 loops

integer no. of loops
0 1
10 2
100 3
1000 4
10000 5
100000 6
1000000 7

Can anybody help how to think? how to read this code so it is a O(log n)?

That is exactly correct.
Your “failure” is just that the input is “n” not “digits in n”.
So how do you calculate the number of digits in a given number base10? Well you calculate the logarithm of the number to the base → so it’s log10(n).

Then that’s some advanced math, but the difference of the base in logarithm is just multiplication with a constant value.

log2(n) === log10(n) * ln(10)/ln(2)

But because in Time-Complexity multiplication with a constant value doesn’t matter, you just use “log(n)”.

Finfact: because the base can be changed, it doesn’t matter that I used ln(x) for the transformation → I could have used any base.

I am trying to understand your words, but didn’t get it yet, revising some stuff about logarithms though, but I wanted to ask you if you may write again in different expressions maybe I can connect some dots.

Let’s take your table and add the logarithmus of base 10 of the integer:

integer no. of loops log10(integer)
0 1 0
10 2 1
100 3 2
1000 4 3
10000 5 4
100000 6 5
1000000 7 6

When the integer n is multiplied by factor of 10, the logarithmus base 10 of it will grow by one → exactly like the loop count.

Oh, I see the pattern now … thank you @Jagaya

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.