CODEWITHSUNDEEP
time-complexitybig-o
rani rawat
rani rawat

Reputation: 35

Why is Time complexity of the code O(log n)?

Here is the code given in the book "Cracking the Coding Interview" by Gayle Laakmann. Here time complexity of the code to find:-

int sumDigits(int n)
{ int sum=0;
 while(n >0)
{
    sum+=n%10;
    n/=10
}
return sum ;
}

I know the time complexity should be the number of digits in n.

According to the book, its run time complexity is O(log n). Book provided brief description but I don't understand.

Upvotes: 2

Views: 1127

Answers (2)

vaibhav kumar
vaibhav kumar

Reputation: 985

The number of times the logic would run is log(n) to the base of 10 which is same as (log(n) to the base 2)/ (log (10) to the base of 2). In terms of time complexity, this would simply be O(log (n)). Note that log(n) to the base of 10 is how you would represent the number of digits in n.

Upvotes: 1

Adnan Isajbegovic
Adnan Isajbegovic

Reputation: 2307

while(n > 0)
{
    sum += n % 10;
    n /= 10;
}

so, how much steps will this while loop take so that n comes to 0? What you do in each step, you divide n with 10. So, you need to do it k times in order to come to 0. Note, k is the number of digits in n.

Lets go step by step: First step is when n > 0, you divide n by 10. If n is still positive, you will divide it by 10. What you get there is n/10/10 or n / (10^2). After third time, its n / (10^3). And after k times, its n/(10^k) = 0. And loop will end. But this is not 0 in mathematical sense, its 0 because we deal with integers. What you really have is |n|/(10^k) < 1, where k∈N.

So, we have this now:

n/(10^k) < 1
n < 10^k
logn < k

Btw. its also n/(10^(k-1)) > 1, so its:

k-1 < logn < k. (btw. don't forget, this is base 10).

So, you need to do logn + 1 steps in order to finish the loop, and thats why its O(log(n)).

Upvotes: 7

Related Questions