algorithm - Run Time Anaysis of Nested Loop - Stack Overflow

admin管理员组

文章数量:1435859

Maybe a bit of a silly question but the run time analysis for this code is confusing me.

int i, j; 
int k = 0;

for(i = 1; i<= n; i*= 2){
    for (j = 1; j <= i; j++){
        k += (i+j);
    }
}

I understand that the outer loops runtime would be log(base2)n and that the overall value of the runtime is the runtime of the outer loop * the runtime of the inner loop. I'm just a little confused about the inner loop, I know the inner loop is iterating based on the value of i.

So would the inner loops runtime also be log(base2)n and then the overall runtime would be (log(base2)n)^2?
Somehow I don't feel like that's right.

Maybe a bit of a silly question but the run time analysis for this code is confusing me.

int i, j; 
int k = 0;

for(i = 1; i<= n; i*= 2){
    for (j = 1; j <= i; j++){
        k += (i+j);
    }
}

I understand that the outer loops runtime would be log(base2)n and that the overall value of the runtime is the runtime of the outer loop * the runtime of the inner loop. I'm just a little confused about the inner loop, I know the inner loop is iterating based on the value of i.

So would the inner loops runtime also be log(base2)n and then the overall runtime would be (log(base2)n)^2?
Somehow I don't feel like that's right.

• algorithm
• time-complexity
• runtime
• big-o

Share Improve this question Follow edited Nov 16, 2024 at 16:52 wohlstad 30.4k1717 gold badges6161 silver badges9494 bronze badges asked Nov 16, 2024 at 2:41 gmargmar 1311 silver badge22 bronze badges 2

• Interesting to analyse while the code looks pre-K&R C. – greybeard Commented Nov 16, 2024 at 5:04
• The complexity analysis depends on whether the int type allows for arbitrary large integers (not just 64-bit). – trincot Commented Nov 16, 2024 at 7:58

Add a comment  | 

3 Answers 3

Sorted by: Reset to default 1

The complexity in this case is determined by the number of times the inner loop will execute, multiplied by the complexity of body of the inner loop.

Regarding the number of times it will execute:
The outer loop will have the values 1,2,4,8,...,n. In each of the outer loop iterations the inner loop will execute times according to this value.
Therefore altogether the inner loop will execute: 1+2+4+8+...+n.

This is a geometric series with a (first element) of 1, r (factor) of 2, and containing log(n) elements.
The formula for the sum of m elements of a geometric series is (r != 1):

Sm = a * (1 - r ^ (m+1)) / (1 - r)

If we assign a=1, r=2, m=log(n) we get:

1 * (1 - 2 ^ (logn+1)) / (1-2) =
1 * (1 - 2 * 2 ^ logn) / (1-2) =
1 * (1 - 2n)) / (-1) =
1 * (2n - 1) =
2*n - 1
=>
O(n)

In this specific case you can also see it as the value of a binary value of logn bits, all set to 1, which is again 2*n - 1 => O(n).

Regarding the body of the inner loop:
It contains a constant amount of calculations and so it is O(1).

=> Therefore the overall complexity is O(n) * O(1) = O(n).

Note:
This assumes that we are dealing with limited size integers (e.g. 64 bit), which is what types like int that you used usually are. If you want to include the analysis for arbitrary large integers up to n, representing and doing operations like addition (which you used) on them becomes O(logn) instead of O(1).

The code has two loops:

Outer Loop:

• Starts with i=1 and multiplies i by 2 each time
• Stops when i becomes larger than n
• So, it runs log2(n) times (since multiplying by 2 repeatedly is the same as dividing n by 2 in reverse).

Inner Loop:

• Runs from j=1 to j=i
• The number of times it runs depends on the value of i
• For example, if i=4, the inner loop runs 4 times

So

• When i=1, the inner loop runs 1 time.
• When i=2, the inner loop runs 2 times.
• When i=4, the inner loop runs 4 times.
• When i=8, the inner loop runs 8 times.

This continues until i reaches n.

total number of iterations of the inner loop is: 1+2+4+8+⋯+n

This means the inner loop runs

本文标签： algorithmRun Time Anaysis of Nested LoopStack Overflow