—> how quickly the running time grows as the input size n increases
We neglect the lower order terms and the coefficients of the highest-order
—> we focus on the highest order because the lower terms become insignificant as the input size grows. As for the coefficients, it is unimportant when it comes to classifying whether it is linear, logarithmic, or quadratic. However, it still affects the running time significantly.
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)
<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:
⇒ 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
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

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: