Analysis of Algorithms and building of Time Equation?

user_14336933 0
Viewed 68

I'm having trouble figuring out the time equation for a couple small snippets of code.

int sum = 0;
for (int k = n; k > 0; k /= 2)
   for (int i = 0; i < k; i++)  
       sum++;

int sum = 0;
for (int i = 1; i < n; i *=2)
   for (int j = 0; j < i; j++) 
       sum++;

int sum = 0;
for (int i = 1; i < n; i *=2)
   for (int j = 0; j < n; j++) 
       sum++;

They're all very similar as you can see. I'm not looking for an exact answer or anything, I'm just not really sure where to start with the inner loops. It seems like they would all run n times, but they can't all be the same, right? I'm pretty sure all of the outer loops would be log(n) and that the sum++ would just be a constant (1), but I'm not really sure how all of the inner loops are different and how that would change the equation.

nested-loops for-loop algorithm java
2 Answers

The third code snippet is the easiest to analyze. For each outer loop iteration the inner loop will make 'n' iterations. Since the number of outer loop iterations is O(log(n)) the total number of iterations (and the complexity of the third snippet) is O(n*log(n)).

The first two code snippets have the same complexity, just the outer loop iterates in the descending order in the first snippet, and in the ascending order in the second one. So you iterate over all powers of two which are smaller than 'n', and then repeat the inner loop the corresponding number of times. The total number of iterations is

1 + 2 + 4 + ... + 2^k

where k=log2(n). Sum of powers of 2 is 2^(k+1)=2*2^k=2*n. So, the complexity in both cases is O(n).

user_129521130 
int sum = 0;
for (int k = n; k > 0; k /= 2)
   for (int i = 0; i < k; i++)  
       sum++;

n + n/2 + n/4 + n/8 + ... + 1 ≈ 2n = Θ(n)

int sum = 0;
for (int i = 1; i < n; i *=2)
   for (int j = 0; j < i; j++) 
       sum++;

1 + ... + n/8 + n/4 + n/2 + n ≈ 2n = Θ(n)
(Well, not exactly ending with n, n/2 etc, but within a factor of 2 of those, so doesn't matter for the complexity class.)

int sum = 0;
for (int i = 1; i < n; i *=2)
   for (int j = 0; j < n; j++) 
       sum++;

n + n + ... + n ≈ log(n) × n = Θ(n log n)

user_167591160
Related