time complexity by just looking at code

Question

Input n Repeat n= n/2 Until n<= 1

i'm not sure whether this has a time complexity of O(n) or O(log n) since n is being halved in every iteration of the loop...

I know that to calculate the time complexity you have to go through each operation and see how many times it will be executed with respect to the input, the part that confuses me is that since we are changing the value of the input with every iteration of the loop, what effect does that have on the total time complexity?

any information about calculating time complexity of algorithms from just looking at code would be appreciated as i still don't quite have a hang of it...

It must be logarithmic as doubling the initial n increases the number of iterations by 1. — Bathsheba, Jun 19 '13 at 14:06

score 1 · Answer 1 · edited May 23 '17 at 12:21

1

To answer the question: Input n Repeat n= n/2 Until n<= 1 is O(logn).

To better answer the question: This is a duplicate: Big O, how do you calculate/approximate it?

edited May 23 '17 at 12:21

Community

1
1

answered Jun 19 '13 at 14:06

000

26,951
10
71
101

time complexity by just looking at code

1 Answers1