int count=0;
do
{
count++;
n=n/2;
}while (n>1);
I'm having trouble seeing the pattern here.
Even when plugging in numbers for n and then plotting out each basic operation.
Thanks in advance!
Edit: I want the worst case here.
Asked
Active
Viewed 572 times
1
Harshit Ruwali
- 820
- 1
- 9
- 20
MorseLane
- 21
- 2
-
4Are you familiar with logarithms? – John Coleman Oct 01 '17 at 23:39
-
1try 2, 4, 8, 16, 32, 64... – luk2302 Oct 01 '17 at 23:40
-
1In practice, it is O(1) because `INT_MAX` is a constant and the growth is so slow. – Raymond Chen Oct 01 '17 at 23:42
-
See: https://stackoverflow.com/questions/9152890/what-would-cause-an-algorithm-to-have-olog-n-complexity – user2205930 Oct 02 '17 at 01:07
1 Answers
3
First step is to divide n with 2. So you get n/2. Now, you divide it again with 2, if n/2 > 1, and you get n/4. If n/4 > 1 you do it again, and you get n/8, or better to write it as n/(2^3)... Now if n/(2^3) > 1 you do it again, and you get n/(2^4)... So, if you do it k times, you get n/(2^k). How to calculate k to so you get n/(2^k) ≤ 1? Easy:
n/(2^k) ≤ 1
n ≤ 2^k
ln(n) ≤ k
So, your algorithm needs O(ln(n)) iterations to exit the loop.
In your code, k is count.
Adnan Isajbegovic
- 2,147
- 15
- 26