Courses‎ > ‎AP Computer Science‎ > ‎Konstantinovich‎ > ‎

2018-11-30 Big O

posted Nov 30, 2018, 6:35 AM by Konstantinovich Samuel   [ updated Nov 30, 2018, 7:20 AM ]
Big-O notation and Run-time Analysis.

Overall Idea:

We are interested in how quickly an algorithm runs relative to the input of the problem. Generally, we think of N as the input size (a list with N elements), but N could be the actual input (such as when calculating the Nth term of a series, or the Nth prime.)

We do not care about an exact number of seconds. Instead, think along the lines:
"How MUCH LONGER does it take when we double N? And when we double N again?"

If the time stays the same, we say it runs in constant time.

If the time increases by a constant factor (double triple or something similar), we say it runs in linear time. The constant (slope of the line) is not important.

We care about very large input sizes, we want to know how the algorithm behaves as N gets "arbitrarily large."


Examples:

//constant time:  O(1)
public int foo(int [] ary){
    return ary[0];
}

//linear time: O(N)
public int foo2(int [] ary){
    int total = 0;
    for( int i : ary){
      total += i;
    }
    return total;
}

//quadratic time O(N^2)
public int foo3(int [] ary){
    int total = 0;
    //outer loop runs N times.
    for( int i = 0; i < ary.length - 1; i++){
        //inner loop runs N times (on average)
        for( int j = 0 ; j < ary.length; j++){   
          //Work Work Work
          total+=i+j+5;
        }
    }
    return total;
}


public int foo4(int [] ary){
    int total = 0;
    //outer loop runs N times.
    for( int i = 0; i < ary.length - 1; i++){
        //inner loop runs N times (on average)
        for( int j = i+1 ; j < ary.length; j++){   
          //Work Work Work
          total+=i+j+5;
        }
    }
    return total;
}
)



NO CONSTANTS
If f(x) is a sum of several terms, if there is one with largest growth rate, it can be kept, and all others omitted. 
Consider the functions:

public int foo2(int [] ary){
    int total = 0;
    for( int i : ary){
      total += i;
    }
    return total;
}

public int foo4(int [] ary){
    int total = 0;
    for( int i : ary){
      total += i;
    }
    for( int i : ary){
      total += i;
    }
    return total;
}


Since they both double the runtime as we double the input size, we consider both
N and 2*N to be just O(N)   where N is the length of the array.

Only count the FASTEST GROWING terms:
If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) can be omitted.

When compared to N we do not worry about a multiplicative constant (e.g. 5*N), so it should follow that we should not worry about a small added constant N + 10.

These are all O(N)
2N+5
3N+200
N + 10000


Similarly:
4N^2 
N^2 + 5N
2N^2 + 10N + 20
Are all considered to be just O(N^2)

The reason is that as N becomes very large, the smaller terms become far less significant.  Consider: When N is a million, the difference between N^2 and 5N is very large, 5N is not significant in terms of the trend of the function as the N grows.

Worst Case:

Sometimes the algorithms we write can stop early. This is great! Except we tend to consider the worst case scenario.

O(N) is an upper bound; in other words the worst case.

Formal Definition (semi formal):

*note that = does not mean equals, it means a more loose 'is' in this case.

You can say that for your function f:
f(x) = O(g(x))  as  x approaches infinity


if and only if there is a positive constant k, that makes:
|f(x)| <= k*|g(x)| for all x >= x0
note:  |f(x)| is how much work your function requires. 

e.g.
Your function f(x) is O(g(x))   if and only if the the runtime of f(x) <= k*|g(x)|
Your function foo() is O(N)  if an only if the runtime of foo() <= k*N
Your function bar is O(N^2) if an only if the runtime of bar() <= k*N^2

Upper Bound:
"<=" means that the big-O notation is an upper bound!
When f(x) is O(N) , it is alo O(N^2) but that is not very useful. We generally want the CLOSEST bound for the runtime!



public static function1(int[]a){
    index = a.length/2;
    while(index > 0){
        System.out.println(a[index]);
        index = a.length/2;
    }
}


Comments