1
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!

Quabs
  • 51
  • 9
  • 1
    Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – 4castle Sep 27 '17 at 04:54
  • Subtract t from the third loop counter, it does not influence a result. Then write down number of internal loops for o=1, 2 and so on. Catch a pattern – MBo Sep 27 '17 at 04:57

2 Answers2

3

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: enter image description here

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

DAle
  • 8,990
  • 2
  • 26
  • 45
  • This comment was very helpful, thank you! Quick question, why does the innermost loop simplify to k=1 to o+1 and not k=1 to o? I thought if you were to simplify that loop by subtracting t it would come out to k=1 to o.... – Quabs Sep 27 '17 at 16:09
  • Is it because if you subtract t from the inner loop it would actually end up being k = 0 to o, which is the same as k=1 to o+1? – Quabs Sep 27 '17 at 16:10
1

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)

marvel308
  • 10,288
  • 1
  • 21
  • 32