CODEWITHSUNDEEP
algorithmbig-otime-complexity
Domi B
Domi B

Reputation: 11

Big-O Estimations | Getting the functions

I'm having troubles understanding how to estimate the Big-O. We've had two lectures on this topic and the only thing I undestand is to take the leading coefficient from the largest polynomial in the function and replace it with an O so it would look like O(...)

During the first lecture this was shown

int i = length;
while (i>0) {
    i--;
    int j = i -1;
    while (j >= 0) {
        if (a[i] == a[j]) {
            return 1;
        }
        j--;
    }
}
return 0;

Followed by this on the following slide

int i = length;                 // Counts as 1
while (i>0) {                   // Counts as N+1
    i--;                        // Counts as N
    int j = i -1;               // Coutns as N
    while (j >= 0) {            // Counts as i+1
        if (a[i] == a[j]) {     // Counts as i
            return 1;
        }
        j--;                    // Counts as i
    }
}
return 0;                       // Counts as 1

From this, I'm wondering why

return 1;

isn't counted as a step.

Following that slide, it tells us that the

Outer Loop count is 3N+1 Inner Loop count is 3i+1 ; for all possible i from 0 to N-1

I understand that the second [while] loop will occur N times and following that, the [if] will occur i times where i is equal to N-1 since if j < 0, the second while loop will still be read but nothing else will happen after it.

The slide shows that the Total from the Inner loop is equal to 3N^2 - 1/2N

and that the Grand Total is equal to 3/2N^2 + 5/2N +3.

Wondering if anyone has time to walk me through how to acquire the functions used in Big-O estimations like in the example above; I have no idea how 3i+1 translated into 3N^2 - 1/2N as well has how the Grand Total is calculated.

Upvotes: 1

Views: 398

Answers (1)

AbcAeffchen
AbcAeffchen

Reputation: 14987

I will try to explain the calculation of the complexity of your example.

First we notice, that every operation requries only constant time, written as O(1), which means, that the run time does not depend on the input.

int i = length;                 // O(1), executed only one time
while (i > 0) {                 // outer loop, condition needs O(1)
    i--;                        // O(1)
    int j = i - 1;              // O(1)
    while (j >= 0) {            // inner loop, condition needs O(1)
        if (a[i] == a[j]) {     // O(1)
            return 1;           // first return statement
        }
        j--;                    // O(1)
    }
}
return 0;                       // second return statement, executed only one time

The number of operations in every loop is constant, so we only have to count how often they are executed.

The outer loop runs from i = n to i = 1. For each i the inner loop is executed once and executes i constant time operations itself. In total we get

 3 + Σi=0,...,n-13 + 3i + 1 = 3 + 4n + 3/2⋅(n-1)⋅n = 3/2⋅n² + 5/2⋅n + 3
(1)           (2) (3)  (4)               (5)

Explanations:

  1. The 3 contains the first line, the last line and the an additional execution of the outer loop condition. The condition evaluates n times to true and one time to false.
  2. This 3 contains one evaluation of the condition of the outer loop and the first two lines in the outer loop.
  3. The factor 3 in front of the i contains one evaluation of the inner loop condition, the evaluation of the if statement and the last line of the inner loop.
  4. The 1 is for the additional evaluation where the inner loop condition evaluates to false.
  5. The sum of consecutive integers 1 to n evaluates to 1/2⋅n⋅(n+1). Notice the sum here is from 0 to n-1, so it evaluates to 1/2⋅(n-1)⋅n.

The frist (inner) return statement is not counted, because if executed the algorithm terminates. But we want to calculate the maximum number of steps, the so called worst case. This case is when the algorithm terminates as late as possible.

Notice: The calculation of the steps is very precise. This is not necessary to get the big-O complexity. It would be enough to say, that each loop runs in O(n) and since they are nested the complexity has to be multiplied so you get O(n)⋅O(n) = O(n²).

Upvotes: 1

Related Questions