Big Theta Notation

Definition

Function r has order of growth $\Theta (g(n))$ if there are positive constants $k_1$ and $k_2$ and a number $n_0$ such that $k_1\cdot g(n)\le r(n)\le k_2\cdot g(n)$ for all $n>n_0$

Explanation

• $\Theta (g(n))$ Specifies the asymptotic bounds (both upper and lower) for a function
• Can be thought of as the average time/space complexity of an algorithm

For CS1101s

1. Identify the basic computational steps
   • Can be thought of as number of function calls in the case of recursive functions (not recursive processes)
2. Try a few small values
3. Extrapolate
4. Watch out for “worst case” scenarios
   • We do not necessarily need to include these scenarios due to $n>n_0$

Some Examples

Function	Time Complexity	Space Complexity
factorial (recursive)	$\Theta (n)$	$\Theta (n)$
factorial (iterative)	$\Theta (n)$	$\Theta (1)$
fibonacci (recursive)	$\Theta ({\Phi }^n)$	$\Theta (n)$
fibonacci (iterative)	$\Theta (n)$?	$\Theta (1)$?