What is the time complexity when dividing by 2 until reaching 1?

Question

i=100
while i>=1:
  i=i//2
  print(i)

What is the time complexity in upper bound for the following code?

Welcome to Stack Overflow! [How to ask homework question](https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions) — Barmar, Nov 03 '20 at 02:34
Please see [How to Ask a Homework Question](https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions). Simply dumping your assignment here is not acceptable. — Prune, Nov 03 '20 at 02:42

samub10 · Answer 1 · 2020-11-03T22:57:17.293

0

If i = 100, i is a constant and hence the time complexity is O(1).

If i is a variable that changes based on the input, then the time complexity is O(log i) as you keep dividing i by 2.

print(i) is executed log i times, hence it does not change the final time complexity.

edited Nov 03 '20 at 22:57

answered Nov 03 '20 at 02:39

samub10

score 0 · Answer 2 · answered Nov 03 '20 at 02:39

Considering that i can change or vary this is a O(log n) logarithmic complexity. (Otherwise, it would be constant time)

The number of loops is logarithmically proportional to the size of i.

See how it scales:

i size  -> # of loops  
10      -> 4
100     -> 7
1000    -> 10
10000   -> 14
100000  -> 17

For reference see how different complexities scale in time:

2 Answers2