2a. Big O

Bubble Sort

Running Time?

Question: how long will it take to run?

Ask instead: how many basic computer operations are needed?

Complexity:

$O(n^2)$ - running time and worst case

Asymptotic Perspective:

Growth rate of worst-case running time as a function of input size.

We say:

• $f(n)=O(g(n))$ if $\exists$c such that $f(n)<=cg(n)$ $\forall n$
• $f(n)=o(g(n))$ if $\frac{f(n)}{g(n)}\to 0$
• $f(n)=w(g(n))$ if $\frac{g(n)}{f(n)}\to 0$
• $f(n)=\theta (g(n))$ if $\exists C,c$ such that $cg(n)<=f(n)<=Cg(n)$

Polynomial Time: $O(n^k)$ for some k Exponential Time: $O(c^n)$ for some c

Interpreting $f(n)=w(g(n))$: $f(n)$ outgrows $g(n)$ as n increases (definition of converging to 0).