Orders of Growth

What

• Provides an abstraction (“rough” measure) of resources used with respect to problem size
  • Resources used can be Time or Space

Important Facts for $g(n)$ (e.g. $\Theta (g(n))$)

• Constants do not matter
  • The constants $k$, $k_1$ and $k_2$ can be adjusted to compensate for constants
• Minor terms do not matter
  • E.g. if $g(n)=n^2+3n+5$, then we can say $\Theta (n^2)$, because we are analysing asymptotic behaviour of the functions
• For certain problems, can be calculated using Master Theorem

When to use $\Theta$, $O$ and $\Omega$

Big theta Is the most strict analysis. Often, for more complex functions, it is difficult to define big theta. This is when we use big O (and occasionally big omega).

Types of Analyses

• Big Theta Notation
• Big O Notation
• Big Omega Notation

Common values of $g(n)$

• $1$
• $\log n$
• $n$
• $n\log n$
• $n^2$
• $n^3$
• $2^n$

Exam Question Examples

$\Theta (2^n)$

function f(n) {
	return n < 1 ? 1 : f(n - 5) + f(n - 5);
}

$\Theta (n^2)$

function f(n) {
	if (n < 1) {
		return 1;
	} else {
		enum_list(1, n); // Theta(n)
		f(n - 5);
	}
}