Compute the complexity of this algorithm:
n-n 0 times
n - n/2 n/2 times
n - n/4 3n/4 times
n - n/8 7n/8 times
n - n/16 15n/16 times
n - 1
n * ((2^n)-1)/(2^n)
n/2 * (a+l)
-n/(2^n) = O(2^n).
You are on the right track. As you mentioned, the inner loop would run
log n times. So, the total number of times it runs is:
(n - n/2) + (n - n/4) + ... (log n) times = n*(log n) - (n/2 + n/4 + n/8 + ... up to 1) = n*(log n) - n*(1/2 + 1/4 + ...) <= n*(log n) - n because (1/2 + 1/4 + ...) is 1 even if we take all terms till infinity (G.P) = n(log n - 1), which is O(n*log(n))
Remember that when calculating complexity, you are always looking for upper bounds, not exact numbers.