This is the code I have been given but I cannot decide whether it is O(log(n)) or O(n).
int i=n;
while (i > 0) {
i/=2;
}
Asked
Active
Viewed 929 times
2
-
1This code cannot compile. Do you mean i/2 == 2 ? – tbsalling Jun 13 '13 at 06:42
-
Looks like homework. How did you try to solve it? – Ilya Kogan Jun 13 '13 at 06:46
-
yes, it is meant to be i/= 2 @MarounMaroun. – user2481063 Jun 13 '13 at 06:49
-
1I believe it is log(n) because it is being divided by 2 at each step and not O(n) as its not from 0 to n – user2481063 Jun 13 '13 at 06:50
-
1You probably wanted to write O(log(n)) and O(n). – mdup Jun 13 '13 at 07:18
1 Answers
5
Lets assume n = 1000.
How many iteration it'll take until i = 0?
Each time you divide it by 2. So we'll get the following table:
Iteration | i
----------|--------
0 | 1000
1 | 500
2 | 250
... | ...
... | ...
10 | 0 <-- Here we stop
Does this help you to figure out the complexity? (It should - Hint: What is ~log(1000) and what does O(n) mean?)
Maroun
- 91,013
- 29
- 181
- 233