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 𝑂(𝑛) times in total when you add up all the work across the outer loop.

The runtime of the entire code is 𝑂(𝑛) because the inner loop dominates the total work done.