What's the time complexity of this? :
for(i=m; i>n; i/=2)
Assume the loop stop at i<=n.
Then taking loop stops at i=n.
i is m/2^k
That is m/2^k = n that's when the loop stop.
What is the big-o notation for this?
Asked
Active
Viewed 79 times
-3
ruakh
- 175,680
- 26
- 273
- 307
Nitesh kumar
- 348
- 2
- 8
- 25
-
[Duplicate](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Prune Mar 20 '19 at 17:56
1 Answers
0
Imagine that m=16. Then each iteration i will be halved, rounding : 16, 8, 4, 2, 1, 0, 0...
Recall that log2(x) is the base 2 logarithm. So log2(2) = 1, log2(4) = 2, log2(8) = 3 and so on. Doubling the number increases the log2 value by 1. Halving the number decreases it by 1.
That means that each step of your loop will decrease the log2 value by 1 until it gets to n.
How many steps does it take to get from m down to n? That is your answer.
Paul Johnson
- 17,438
- 3
- 42
- 59