complexity-theory - T(n) = Θ 格式的计算复杂度

Question

有人可以解释这段代码的大θ格式的复杂性是什么（以及为什么）？这是我从这个主题的第一个任务，我有点困惑。任何形式的帮助将不胜感激！

for i <-- 1 to n-1
   do j <-- 1
     while j <= 2*(i+1)
       do j <-- j + 1

Answer 1

First of all your Pseudocode is not exactly correct according to the usual conventions.

for i <-- 1 to n-1
   do j <-- 1
     while j <= 2*(i+1)
       do j <-- j + 1

The above pseudocode should be more clear if represented as follows,

for i = 1 to n-1
    for j = 1 to (2*(i+1))
        // Body of the inner loop

The complexity of the above pseudocode can be analyzed only if the body of the inner loop contains constant time expressions. For example an addition or subtraction is a constant time operation if the operands are small enough. On the other hand if the loop contains a call to another function then the complexity also depends on the complexity of this called function.

If the body of the loop only contains constant time expressions then the complexity can be analyzed as follows.

The outer loop executes n-1 times. The inner loop executes 2*(i+1) times.

So the statements inside the inner loop gets executed 4, 6, 8, ..., and finally 2n times. So the total number of instructions executed is,

4 + 6 + 8 + ... + 2n
= 2 ( 2 + 3 + 4 + ... + n)
= 2 (n(n+1)/2 - 1)
= n(n+1) - 2

There for the total number of instructions executed is , n² - n - 2.

Thus the complexity is Θ(n²).

Answer 2

I could be wrong with a ±1, but i think that the number of steps that will be executed is:

sum_{i=1}^{n-1} 2*(i+1) = 2sum_{i=1}^{n-1} + 2(n-1) = (n^2-n) + (2n-1) = n^2+n+1

Answer 3

n^2 because you have a loop in a loop, so that means your instructions are executed n * n times