Menu
The problem
Compute the complexity of this algorithm:
for(i=n; i>1;i=i/2)
for(j=i;j<n;j++){
statement;
}
What have I done on this topic before:
The first loop runs logn times. The second loop runs n-i times with i starting from n and changing to i/2 in each outer loop iteration. So the inner loop runs like this:
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
and so on till
n - 1 times
so the general term is n * ((2^n)-1)/(2^n)
Now this sequence is not arithmetic nor geometric. So formula of n/2 * (a+l) cannot be applied on it. How do I further proceed with this solution or if it is wrong, then what is the correct method.
Note: If n/2*(a+l) is applied, the resulting complexity is -n/(2^n) = O(2^n).
792
Two nested loops: O(n²) At each step of the iteration, the nested loop is doing an O(1) operation. So overall time complexity = O(n²) * O(1) = O(n²).
So we can say the complexity of each for loop is O(n) as each loop will run n times. So you specified these loops are not nested in a linear scenario for first loop O(n)+ second loop O(n)+ third loop O(n) which will give you 3O(n) .
This nested loop will have time complexity as O (n^2). Because the outer for loop will run n times and for each iteration, the inner for loop will also run for n times.
Consider following simple example where we have single for loop with 1 static statement within it: Formula to calculate overall complexity of a loop is: sum of (number of iterations * (number of static statements or dynamic statements)) Let's take another example, consider following program and find out it's overall complexity:
For example, the following loop is O (1). 2) O (n): Time Complexity of a loop is considered as O (n) if the loop variables are incremented/decremented by a constant amount. For example following functions have O (n) time complexity.
4) O (Logn) Time Complexity of a loop is considered as O (Logn) if the loop variables are divided/multiplied by a constant amount. For example, Binary Search (refer iterative implementation) has O (Logn) time complexity. Let us see mathematically how it is O (Log 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.
193
First the calculations
A := (n - n) + (n - n/2) + (n - n/4) + ... + (n - n / 2^logn) =
log n * (n) - n * (1 + 1/2 + 1/4 + 1/8 + .... 1 / 2 ^ logn)
A > log n * (n) - n * (1 + 1/2 + 1/4 + 1/8 + .... + 1 / 2^infity) =
logn * n - n = n(logn - 2)
A < log n * (n)
As you see I have assigned the expression you want to evaluate to A. From the last two inequations it follows the complexity of your algorithm is thetha(n logn)
Here I used the well known geometric progression of (1 + 1/2 + 1/4 + .....) = 2
45
The exact no of times the statement runs is nlogn - 2n(1-1/2^logn)
1
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
