Running time and Order of growth:

—> how quickly the running time grows as the input size n increases

Asymptotic Analysis studies the behavior of functions in the limit

Big-O:

How bad can it get?

if both f and g are positive functions, if g creates an upper bound (f is less than or equal to g) then we say

$f=O(g)$ s.t. ∀n≥ a:

$$ 0≤ f(n) ≤ c*g(n) $$

$$ \begin{equation*}0\leq \lim_{n\to\infty} \frac{f(n)}{g(n)} < \infty \end{equation*} $$

Big-Ω :

As good as it gets

if both f and g are positive functions, if g creates a lower bound (f is greater than or equal to g) then we say

$f=Ω(g)$ s.t. ∀n≥ a:

$$ 0≤c*g(n)≤f(n) $$

$$ \begin{equation*}0<\lim_{n\to\infty} \frac{f(n)}{g(n)} \leq \infty \end{equation*} $$

—> we can prove/disprove either by picking a constant that satisfies the inequality or if the two functions are from different classes then we aim to make one side a constant, think $2^n= O(4^n)$ or $n+1 = O((n+1)!)$

Big-Θ :

no better and no worse

$$ f=O(g) \wedge f=Ω(g) \leftrightarrow f=Θ(g) $$

In other words, if we have a function g if multiplied by a constant it creates an upper bound to f and if multiplied by another constant it creates a lower bound to f then it is considered big theta.

(creates both an upper and lower bound based on the constant g is multiplied with)

$$ \begin{equation*}0<\lim_{n\to\infty} \frac{f(n)}{g(n)} < \infty \end{equation*} $$

Small-o and small-ω :

strictly worse or strictly better

We omit the equality from the inequalities, it is either more than or less than g.

(if $f=Θ(g)$ then it immediately means that f has neither small o nor ω)

for small-o as it is strictly less, g is greater as an increases:

$$ \begin{equation*}\lim_{n\to\infty} \frac{f(n)}{g(n)}=0 \end{equation*} $$

and for small-ω it is the opposite with the numerator greater than the denominator, going to infinity:

$$ \begin{equation*}\lim_{n\to\infty} \frac{f(n)}{g(n)}=\infty\end{equation*} $$

Tilde ~ notation :

If $\frac{f(n)}{g(n)}$ approaches 1 as n approaches infinity we say $f(n) \sim g(n)$

(the two functions are equal, including the coefficients, after dropping the lower order terms)

  1. Reflexivity: f=O(f)
  2. if f=O(g) then c*f is also said to be O(g)
  3. Transitivity: if f=O(g) and g=O(h) then f=O(h)
  4. if f1=O(g1) and f2=O(g2) then f1+f2=O(max{f1,f2})
  5. Symmetry: f=Θ(g) and g=Θ(f)
  6. Transpose Symmetry: f=O(g) if and only if g=Ω(f) also f=Ω(g) if and only if g=O(f)

<aside> ⚠️ It is more correct to say f belongs to $\in$ instead of equal to since $O(g)$ is a set of functions.

</aside>

A minor recap:

Notes to consider:

  1. Some algorithms could have the same worst-case. However one is much faster than the other. (Same curve but affected by other factors like hardware, software, coefficients etc. )
  2. Although some algorithms could have a worse worst-case than others. In practice it could be much faster since the likelihood of the worst-case is less.

⇒ thus the actual running time of an algorithm could differ from its order of growth.

Analytical Combinatorics because why stop at an upper bound :P


Design Technique: Divide and Conquer !!

Honorable Mention: The Bisection Method in Numerical Analysis

⇒ when you recursively break the problem into two sub-problems until they are simple enough to solve directly

Merge sort:

Majority of the work is done in merging the two subarrays whereas the actual partitioning is straightforward by finding the mid index and recursively calling the function at either sides.

The running time is $\theta(n+m)$ data compares and array accesses.

The best case is $\theta(min(n,m))$ and the worst case is $\theta(n)$

⇒ Generally for a merge-sort functioning, we have a linear order of growth with best of $\frac{n}{2}$ and worst of $n-1$

$T(n)=T(\frac{n}{2}) +T(\frac{n}{2})+\theta(n)=\theta(nlogn)$

⇒ Because of the structural similarities to a tree, we ask; how many steps do we need to go from n to 1 while also doing a linear operation at each level? Resulting in the height of the tree times the linear operation

merge_sort(array, first, last) {
if first>= last return

mid= first + (last-first)/2

merge_sort( array, first, mid)
merge_sort( array, mid+1, last)

merge( array, first, mid, last)
}
merge (array, first, mid, last){

array result[last-first+1] 
 k=0, j=mid+1, i=first

for( k=0; k< size; k++ )
if(i>mid)
				 result[k]=array[j++]
else if (j>last)
				 result[k]=array[i++]
else if (array[i]<=array[j]) 
			 	result[k]=array[i++]
else result[k]= array[j++]

copy result into the array
}

Optimization of merge sort: