How would you go about finding the complexity of t

问题:

function alg1(n)
1 a=0
2 for o=1 to n do
3     for t=1 to o do
4         for k=t to o+t do
5         a=a+1
6 return(a)

If anyone could guide me to how you would find the worst-case here, and how to get the output a of alg1 as a function of n, I would be very grateful. Thanks!

回答1:

We can compute the exact number of increments this code executes. First, let's replace

for k=t to o+t do

with

for k=1 to o+1 do 

After this change, two inner loops looks like this

for t=1 to o do
    for k=1 to o+1 do

The number of iterations of these loops is obviously o*(o+1). The overall number of iterations can be calculated in the following way:

We can exclude coefficients and lower order terms of the polynomial when using big-O notation. Therefore, the complexity is O(n^3).

回答2:

Subtract t from the last loop so that it becomes

for k=0 to o do

Now the 2 inner most loops would run for O(o^2) time for every value of o. The answer would be

1^2 + 2^2 + ... n^2

which is equal to

n(n+1)(2n+1)/6. Hence it would be of order of O(n^3)