How to derive the big O of this algorithm?

Question

This is the algorithm:

for i ← 1 to n by 1 do
    for j ← 1 to i by 1 do
        for k ← 1 to j by 1 do
           x = x + 1
        end
    end
end

The number of times the inner loop iterate, depends on the outer loops... so how can the time complexity be derived?

Answer 1

This algorithm increases 𝑥 with the 𝑛^th tetrahedral number. This is because the loops can be seen as sums over a range:

• The outer loop: ∑_𝑖^𝑛_{= 1}
• The middle loop: ∑_𝑗^𝑖_{= 1}
• The inner loop: ∑_𝑘^𝑗_{= 1}
• The inner statement: runs in constant time, so that counts as 1 operation.

This means the inner statement runs this many times:

∑_𝑖^𝑛_{= 1} ( ∑_𝑗^𝑖_{= 1} ( ∑_𝑘^𝑗_{= 1} 1 ) )

The inner sum really is 𝑗, so we can write:

∑_𝑖^𝑛_{= 1} ( ∑_𝑗^𝑖_{= 1} 𝑗 )

We recognise this expression as the tetrahedral number (see formula at above link to Wikipedia)

This double sum is 𝑛(𝑛 + 1)(𝑛 + 2)/6 = θ(𝑛³)

Another way to see this, is that the loops lead to combinations for 𝑖, 𝑗, and 𝑘 where they appear in non-decreasing order. So the number of times x = x + 1 is executed, corresponds to the number of ways we can select a multiset of three values from the range 1..𝑛, allowing duplicates. This number is "𝑛 multichoose 3", which leads to the same formula.