Time Complexity of An Algorithm That Includes While Loop

Question

How to analyze the running time of foo function with asymptotic notations?

I thought like that : i=0 is constant time, n%2==0 is constant time, n=n/2 is constant time, i++ is constant time.But I can't say that "while loop run n times".Becasue of n=n/2 expression.

I don't know repeat number of this while loop.For example , if n is 5 ,while loop don't run, if b is 4 , while loop will run 2 times. if b is 14 , while loop will still run 2 times.

 foo(n):
 i=0
 while(n%2==0)
 n=n/2
 i++
 return i

• Lee Daniel Crocker: For any n, n/2 will reach 0 in at most log2(n) steps, so the loop is O(log2(n))

Answer 1

It is better to look Best, worst and average case. In your problem, Best case have a constant time O(1), worst case and average case both have O(log(n)) time. Best case is obvious, it is when number if odd. Worst case is obvious too, it happens when your number is like n=2^k. You average is happens if your number is something like n=p*2^k where p is odd. But running time in this case is similar to worst case, because number of loop iterations goes down by dividing your range by 2.

You can analyze this code similar to Binary Search Algorithm. Even though you may find result in first compare, the average case has a O(log(n)) running time.

Regards

• Dijital Dünya: Thanks a lot, also Could you explain that how to find log(n) and why best case is O(n)? I think it should be omega(n) .
• Afshin: best case is O(1) not O(n). O(1) means constant time and happens when loop does not run. It means it happens if you pass odd number.
• Dijital Dünya: Oh, sorry , I misspelled . why not omega(1)?