1

How do you compute the worst case time complexity of this algorithm

for j = 1 to i do
     for k = 1 to j do 
         print(i,j,k)
MrEricSir
  • 8,044
  • 4
  • 30
  • 35
bluejace
  • 33
  • 4
  • Examine the code, and figure out how many operations it needs to do for a fixed value of `i`. (What is `i`?) Are you missing something after the first `=`'? – Andrew Jaffe Mar 09 '16 at 23:30
  • Possible duplicate of [How to find time complexity of an algorithm](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – jaypb Mar 09 '16 at 23:31
  • `j = to i` What does that mean? And what is the complexity of `print`? And what do you mean by "worst case"? There are no cases here. – Baum mit Augen Mar 09 '16 at 23:31
  • 1
    The inner loop iterates to ``i/2`` on average. So you yield: ``i * i/2 -> i^2 / 2 -> O(i^2)`` – BitTickler Mar 09 '16 at 23:31
  • @AndrewJaffe, oh yeah, I missed 1 – bluejace Mar 09 '16 at 23:32
  • I'm voting to close this question as off-topic because this is more appropriate for cs.stackexchange.com. – Barmar Mar 10 '16 at 00:51

1 Answers1

0

Since we have no conditions which would affect the runtime of this algorithm the complexity would remain the same: there is always the same time complexity.

Let's keep it simple.

If we do just consider the semantic important instruction in the inner loop we can calculate the complexity as followed:

Every outer loop run increases the next inner loop run count by one.

We would have 1 + 2 + 3 + 4 + 5 + ... + i-1 + i loop runs, everytime the outer loop finished, the inner loop will be executed one more time than before.

Now we try to generalize this expression.

We double the initial term to represent it in an alternative form, you'll recognize why.

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) + (1 + 2 + 3 + 4 + 5 + ... + i-1 + i)

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = (1+i) + (2 + (i-1)) + (3 + (i-2)) + ... + ((i-1) + 2) + (i+1)

Now we can see that in this representation we have a multiple of the same term.

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = (1+i) + (1+i) + (1+i) + ... + (1+i) + (1+i)

2 * (1 + 2 + 3 + 4 + 5 + ... + i-1 + i) = i*(1+i)

Since we still have the double of our initial complexity, we need to divide by 2, which results in closed-form expression.

1 + 2 + 3 + 4 + 5 + ... + i-1 + i = (i*(1+i))/2

resulting in our complexity O(i(i+1)/2) => O(i^2)

We can do so due to the fact that given a polynomial inside an O() you can simply replace it with x^highest_power

We don't take care of the instructions which are mandatory processed by the control structures itself; I do not think this is the task. If you desire so, please let me know.

Noli
  • 604
  • 2
  • 10
  • 27