Big O

• Lots of different ways to solve a problem: which is best?
• Measure algorithmic efficiency
  • how many resources (time? memory? battery power? etc.) does the program use
  • We will focus on time. Many other resources, such as battery power are often directly related to time
• Idea: algorithms are better if they take less time
• Problem: amount of time a program takes is variable
  • Depends on what computer you are using, what other programs are running, whether your phone/laptop is connected to a power source, etc...

Big O

• Idea: assume each statement of code takes some unit of time. For the purposes of this class, that unit does not matter
• We can count the number of units of time and get the runtime
• Sometimes, the number of statements depends on the input -- we'll say the input size is N. e.g., N elements in the vector

Example

statement1;                         // runtime = 1 
for (int i = 1; i <= N; i++) {      // runtime = N^2 
    for (int j = 1; j <= N; j++) {  // runtime = N 
        statement2; 
    } 
} 
for (int i = 1; i <= N; i++) {      // runtime = 3N 
    statement3; 
    statement4; 
    statement5; 
}                                   // total = N^2 + 3N + 1 

The actual constant does not matter --- remember that we haven't even specified how much a unit of time is --- so we get rid of constants:

N^2 + 3N + 1 --> N^2 + N + 1

Only the biggest power of N matters:

N^2 + N + 1 --> N^2

• The biggest term grows so much faster than the other terms that the runtime of that term "dominates"
• Another way to think about it:

  N^2 + N + 1 < 2N^2
  

  when N is big, and we already said we don't care about constants
• We would then say the code snippet has O(N^2) runtime.

Finding Big O

• Work from the inner-most indented code out
• Realize that some code statements are more costly than others
  • It takes O(N^2) time to call a function with runtime O(N^2), even though calling that one function is only one line of code
• Nested code multiplies
• Code at the same indentation level adds

What is the Big O?

int sum = 0; 
for (int i = 1; i < 100000; i++) { 
    for (int j = 1; j <= i; j++;) { 
        for (int k = 1; k <= N; k++) { 
            sum++; 
        } 
     } 
} 
Vector v; 
for (int x = 1; x <= N; x += 2) { 
    v.insert(0, x); 
} 
cout << v << endl; 

Complexity class: a category of algorithmic efficiency based on the algorithm's relationship to the input size "N".

Example complexity classes

Class	Big-Oh	If you double N, ...	Example
constant	O(1)	unchanged	10ms
logarithmic	O(log_2 N)	increases slightly	175ms
linear	O(N)	doubles	2.1 sec
log-linear	O(N log_2 N)	slightly more than doubles	9 secs
quadratic	O(N^2)	quadruples	1 min 42 secs
quad-linear	O(N^2 log_2 N)	slightly more than quadruple	8 mins
cubic	O(N^3)	multiplies by 8	55 mins
...	...	...	...
exponential	O(2^N)	multiplies drastically	5*10^61 years
factorial	O(N!)	multiplies drastically	10^200 years