Running Time Calculation/Complexity of an Algorithm

Question

I have to calculate the time complexity or theoretical running time of an algorithm (given the psuedocode), line by line as T(n). I've given it a try, but there are a couple things confusing me. For example, what is the time complexity for an "if" statement? And how do I deal with nested loops? The code is below along with my attempt which is commented.

length[A] = n

    for i = 0 to length[A] - 1    // n - 1 
      k = i + 1                   // n - 2
      for j = 1 + 2 to length[A]  // (n - 1)(n - 3)
        if A[k] > A[j]            // 1(n - 1)(n - 3)
          k = j                   // 1(n - 1)(n - 3)
      if k != i + 1               // 1(n - 1)
        temp = A[i + 1]           // 1(n - 1)
        A[i + 1] = A[k]           // 1(n - 1)
        A[k] = temp               // 1(n - 1)

I got O(n^2). Your if statement can be disregarded, as it doesn't alter the flow of the loop. Your inner loop doesn't depend on the outer loop, so they run (n - a) * (n - b) = n^2 + ... times for a given n. — Blender
– Blender, Commented Jan 22, 2013 at 3:50

rainer · Accepted Answer · 2013-01-23 12:12:17Z

Blender is right, the result is O(n^2): two nested loops that each have an iteration count dependent on n.

A longer explanation:

The if, in this case, does not really matter: Since O-notation only looks at the worst-case execution time of an algorithm, you'd simply choose the execution path that's worse for the overall execution time. Since, in your example, both execution paths (k != i+ 1 is true or false) have no further implication for the runtime, you can disregard it. If there were a third nested loop, also running to n, inside the if, you'd end up with O(n^3).

A line-by-line overview:

for i = 0 to length[A] - 1    // n + 1 [1]
  k = i + 1                   // n
  for j = 1 + 2 to length[A]  // (n)(n - 3 + 1) [1]
    if A[k] > A[j]            // (n)(n - 3)
      k = j                   // (n)(n - 3)*x [2]
  if k != i + 1               // n
    temp = A[i + 1]           // n*y [2]
    A[i + 1] = A[k]           // n*y
    A[k] = temp               // n*y

[1] The for loop statement will be executed n+1 times with the following values for i: 0 (true, continue loop), 1 (true, continue loop), ..., length[A] - 1 (true, continue loop), length[A] (false, break loop)

[2] Without knowing the data, you have to guess how often the if's condition is true. This guess can be done mathematically by introducing a variable 0 <= x <= 1. This is in line with what I said before: x is independent of n and therefore influences the overall runtime complexity only as a constant factor: you need to take a look at the execution paths .

Collectives™ on Stack Overflow

Running Time Calculation/Complexity of an Algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related