'Algorithmic Complexity - Difficulty Understanding Example
Here are the two loops for reference, could someone please explain how the second nested loop is theta(n)? I understand the outside loop is iterating log n times as the incrementer is compound assigning to itself and multiplying by 2 effectively becomin some value 2 to the power of x but is less than n. So then on the inside loop we are effectively iterating k times for each power of 2 increase, would that not mean the the number of operations would be log(n)? I found other explanations but they still don't effectively help break it down. Thanks for any help in advance.
sum1 = 0;
for (k=1; k<=n; k*=2) // Do log n times
for (j=1; j<=n; j++) // Do n times
sum1++;
sum2 = 0;
for (k=1; k<=n; k*=2) // Do log n times
for (j=1; j<=k; j++) // Do k times
sum2++;
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|