Big O

Question 1

What is Big O?

Answer 1

The language and metric we use to describe the efficiency of algorithms

Question 2

What is best case runtime?

Answer 2

If all elements are equal, then quick sort will, on average, just traverse the array once. This is O(N).

Question 3

What is worst case runtime?

Answer 3

Getting really unlucky and having to traverse the entire array many times…This is O(N^2).

Question 4

What is expected case runtime?

Answer 4

If the worst case doesn’t happen over and over again…this is O(N log N).

Question 5

What are the steps in determining runtime?

Answer 5

1. Drop the Constants.
2. Drop the non-dominant terms.
3. Consider multi-part algorithms (add vs multiply).

Question 6

Which one is faster?

Min and Max1
1. int min = Integer.MIN_VALUE;
2. int max = Integer.MIN_VALUE;
3. for (int x : array) {
   if ( x < min ) min = x;
   if ( x > max) max = x;
}

Answer 6

Min and Max2
1. int min = Integer.MIN_VALUE;
2. int max = Integer.MIN_VALUE;
3. for (int x : array) {
   if ( x < min ) min = x;
}
4. for ( int x : array) {
     if ( x > max) max = x;
}

Question 7

What is the hierarchy of dominant terms?

Answer 7

1. O(n!)
2. O(2^n)
3. O(n^2)
4. O(n log n)
5. O(n)
6. O(log n)

Question 8

What is an example of O(log N) runtime?

Answer 8

Binary search algorithm…when you see a problem where the number of elements in the problem space gets halved each time.

Question 9

Formally speaking, what is the formula for Big-O notation?

Answer 9

If F and G are functions, then F = O(G) if there exists some constant, C, such that |F(x)| <= C * |G(x)| for sufficiently large x.

In the equality case, when |F(x)| = C * |G(x)| for sufficiently large x, f = O(g).