Growth of Functions
 We will use something called bigO notation (and some siblings described later) to describe how a function grows.
 What we're trying to capture here is how the function grows.
 … without capturing so many details that our analysis would depend on processor speed, etc.
 … without worrying about what happens for small inputs: they should always be fast.
 For functions \(f(x)\) and \(g(x)\), we will say that “\(f(x)\) is \(O(g(x))\)” [pronounced “\(f(x)\) is bigoh of \(g(x)\)”] if there are positive constants \(C\) and \(k\) such that
\[f(x) \le Cg(x)\text{ for all }x>k\,.\]
 The bigO notation will give us a orderofmagnitude kind of way to describe a function's growth (as we will see in the next examples).
 Roughly speaking, the \(k\) lets us only worry about big values (or input sizes when we apply to algorithms), and \(C\) lets us ignore a factor difference (one, two, or ten steps in a loop).
 I might also say “\(f(x)\) is in \(O(g(x))\)”, then thinking of \(O(g(x))\) as the set of all functions with that property.
Example: The function \(f(x)=2x^3+10x\) is \(O(x^3)\).
Proof: To satisfy the definition of bigO, we just have to find values for \(C\) and \(k\) that meet the condition.
Let \(C=12\) and \(k=2\). Then for \(x>k\), \[\begin{align*} 2x^3+10x &= 2x^3+10x\\ &< 2x^3+10x^3\\ &= 12x^3.\quad ∎ \end{align*}\]
 Note: there's nothing that says we have to find the best \(C\) and \(k\). Any will do.
 Also notice that the absolute value doesn't usually do much: since we're worried about running times, negative values don't usually come up. We can just demand that \(x\) is big enough that the function is definitely positive and then remove the \(\cdots\).
 Now it sounds too easy to put a function in a bigO class. But…
Example: The function \(f(x)=2x^3+10x\) is not in \(O(x^2)\).
Proof: Now we must show that no \(C\) and \(k\) exist to meet the condition from the definition.
For any candidate \(C\) and \(k\), we can take \(x>k\) and \(x>0\) and we would have to satisfy \[\begin{align*} 2x^3+10x &< Cx^2 \\ 2x^3+10x &< Cx^2 \\ 2x^3 &< Cx^2 \\ x &< C/2 \\ \end{align*}\]
So no such \(C\) and \(k\) can exist to let the inequality hold for large \(x\).∎
Example: The function \(f(x)=2x^3+10x\) is \(O(x^4)\).
Proof idea: For large \(x\), we know that \(x^4>x^3\). We could easily repeat the \(O(x^3)\) proof above, applying that inequality in a final step.

Example: The function \(f(x)=5x^2  10000x + 7\) is \(O(x^2)\).
Proof: We have to be a little more careful about negative values here because of the “\( 10000x\)” term, but as long as we take \(k\ge 2000\), we won't have any negative values since the \(5x^2\) term is larger there.
Let \(C=12\) and \(k=2000\). Then for \(x>k\), \[\begin{align*} 5x^2  10000x + 7 &= 5x^2  10000x + 7\\ &< 5x^2 + 7x^2\\ &= 12x^2.\quad ∎ \end{align*}\]
 It probably wouldn't take many more proofs to convince you that \(x^n\) is always in \(O(x^n)\) but never in \(O(x^{n1})\).
 We can actually do better than that…
 The bigO operates kind of like a \(\le\) for growth rates.
BigO Results

Theorem: Any degree\(n\) polynomial, \(f(x)=a_nx^n + a_{n1}x^{n1}+\cdots + a_1x+a_0\) is in \(O(x^n)\).
Proof: As before, we can assume that \(x>1\) and then, \[\begin{align*} f(x) &= a_nx^n + a_{n1}x^{n1}+\cdots + a_1x+a_0 \\ &\le a_nx^n +a_{n1}x^{n1}+\cdots + a_1x+a_0 \\ &= x^n(a_n +a_{n1}/x+\cdots + a_1/x^{n1}+a_0/x^n) \\ &\le x^n(a_n +a_{n1}+\cdots + a_1+a_0)\,. \end{align*}\]
Now, if we let \(C=\sum a_i\) and \(k=1\), we have satisfied the definition for \(O(x^n)\).∎

Theorem: If we have two functions \(f_1(x)\) and \(f_2(x)\) both \(O(g(x))\), then \(f_1(x)+f_2(x)\) is also \(O(g(x))\).
Proof: From the definition of bigO, we know that there are \(C_1\) and \(k_1\) that make \(f_1(x) \le Ch(x)\) for \(x>k_1\), and similar \(C_2\) and \(k_2\) for \(f_2(x)\).
Let \(C=C_1+C_2\) and \(k=\mathrm{max}(k_1,k_2)\). Then for \(x>k\), \[\begin{align*} f_1(x)+f_2(x) &\le f_1(x)+f_2(x) \\ &\le C_1g(x) + C_2g(x) \\ &= Cg(x) \,. \end{align*}\]
Thus, \(f_1(x)+f_2(x)\) is \(O(g(x))\).∎
 The combination of functions under bigO is generally pretty sensible…

Theorem: If for large enough \(x\), we have \(f(x)\le g(x)\), then \(f(x)\) is \(O(g(x))\).
 Sometimes the bigO proof is even easier.

Theorem: If we have two functions \(f_1(x)\) which is \(O(g_1(x))\) and \(f_2(x)\) which is \(O(g_2(x))\), then \(f(x)+g(x)\) is \(O(\mathrm{max}(g_1(x),g_2(x)))\).
 When adding, the bigger one wins.

Theorem: If we have three functions \(f,g,h\) where \(f(x)\) is \(O(g(x))\) and \(g(x)\) is \(O(h(x))\), then \(f(x)\) is \(O(h(x))\).
 Approximately: if \(h\) is bigger than \(g\) and \(g\) is bigger than \(f\), then \(h\) is bigger than \(f\).

Corollary: Given \(f_1(x)\) which is \(O(g_1(x))\) and \(f_2(x)\) which is \(O(g_2(x))\) and \(g_1(x)\) is \(O(g_2(x))\) then \(f_1(x)+f_2(x)\) is \(O(g_2(x))\).
 That is, if we have two functions we know a bigO bound for, and we add them together, we can ignore the smaller one in the bigO.

Theorem: If we have two functions \(f_1(x)\) which is \(O(g_1(x))\) and \(f_2(x)\) which is \(O(g_2(x))\), then \(f(x)g(x)\) is \(O(g_1(x)g_2(x))\).
 Multiplication happens in the obvious way.

Theorem: Any constant value is is \(O(1)\).
 Aside: You will often hear a constant running time algorithm described as \(O(1)\).

Corollary: Given \(f(x)\) which is \(O(g(x))\) and a constant \(a\), we know that \(af(x)\) is \(O(g(x))\).
 That is, if we have a function multiplied by a constant, we can ignore the constant in the bigO.

 All of that means that it's usually pretty easy to guess a good bigO category for a function.
\(f(x)=2^x+x^2\) is in \(O(\mathrm{max}(2^x,x^2))=O(2^x)\), since \(2^x\) is larger than \(x^2\) for large \(x\).
\(f(x)=\frac{1}{100}x^{12} + 100x^{11}  87\) is in \(O(x^{12})\).
 Directly from the theorem about polynomials.
 For small \(x\), the \(100x^{11}\) is the largest, but as \(x\) grows, the \(\frac{1}{100}x^{12}\) term takes over.
\(f(x)=14x2^x + x\) is in \(O(x2^x)\).
 What is a good bigO bound for \(17x^4  12x^2 + \log_2 x\)?
 We can start with the obvious: \[17x^4  12x^2 + \log_2 x \text{ is in } O(17x^4  12x^2 + \log_2 x)\,.\]
 From the above, we know we can ignore smallerorder terms: \[17x^4  12x^2 + \log_2 x \text{ is in } O(17x^4)\,.\]
 And we can ignore leading constants: \[17x^4  12x^2 + \log_2 x \text{ is in } O(x^4)\,.\]
 The “ignore smallerorder terms and leading constants” trick is very useful and comes up a lot.
BigΩ
 As mentioned earlier, bigO feels like \(\le\) for growth rates.
 … then there must be \(\ge\) and \(=\) versions.
 We will say that a function \(f(x)\) is \(\Omega(g(x))\) (“bigomega of \(g(x)\)”) if there are positive constants \(C\) and \(k\) such that when \(x\gt k\),\[f(x) \ge Cg(x)\,.\]
 This is the same as the bigO definition, but with a \(\ge\) instead of a \(\le\).

Example: The function \(3x^2+19x\) is \(\Omega(x^2)\).
Proof: If we let \(C=3\) and \(k=1\) then for \(x>k\), \[\begin{align*} 3x^2+19x &\ge 3x^2+19x \\ &\ge 3x^2\,. \end{align*}\]
From the definition, we have that \(3x^2+19x\) is \(\Omega(x^2)\).∎
 As you can guess, the proofs of bigΩ are going to look just about like the bigO ones.
 We have to be more careful with negative values: in the bigO proofs, we could just say that the absolute value was bigger and ignore it. Now we need smaller values, so can't be so quick.
 But the basic ideas are all the same.

Theorem: \(f(x)\) is \(O(g(x))\) iff \(g(x)\) is \(\Omega(f(x))\).
Proof: First assume we have \(f(x)\) in \(O(g(x))\). Then there are positive \(C\) and \(k\) so that when \(x\gt k\), we know \(f(x)\le Cg(x)\). Then for \(x\gt k\), we have \(g(x)\ge \frac{1}{C}f(x)\) and we can use \(k\) and \(\frac{1}{C}\) as constants for the definition of bigΩ.
Similarly, if we assume that \(g(x)\) is \(\Omega(f(x))\), we have positive \(C\) and \(k\) so that when \(x\gt k\), we have \(g(x)\ge Cf(x)\). As above we then have for \(x\gt k\), \(f(x)\le\frac{1}{C}g(x)\).∎
BigΘ
 We will say that a function \(f(x)\) is \(\Theta(g(x))\) (“bigtheta of \(g(x)\)”) if \(f(x)\) is both \(O(g(x))\) and \(\Omega(g(x))\).
 For a function that is \(\Theta(g(x))\), we will say that that function “is order \(g(x)\).”

Example: The function \(2^x+x^2\) is order \(2^x\).
Proof: To show that \(2^x+x^2\) is \(O(2^x)\), we can take \(C=2\) and \(k=4\). Then for \(x>k\), \[\begin{align*} 2^x+x^2 &= 2^x+x^2 \\ &\le 2\cdot 2^x\,. \end{align*}\]
To show that \(2^x+x^2\) is \(\Omega(2^x)\), we can use \(C=1\) and \(k=1\). For \(x>k\), \[\begin{align*} 2^x+x^2 &= 2^x+x^2 \\ &\ge 2^x\,. \end{align*}\]
Thus, \(2^x+x^2\) is \(\Theta(2^x)\).∎
 The above theorem gives another way to show bigΘ: if we can show that \(f(x)\) is \(O(g(x))\) and \(g(x)\) is \(O(f(x))\), then \(f(x)\) is \(\Theta(g(x))\).

Theorem: Any degree\(n\) polynomial with \(a_n\ne 0\), \(f(x)=a_nx^n + a_{n1}x^{n1}+\cdots + a_1x+a_0\) with \(a_n\gt 0\) is in \(\Theta(x^n)\).
 A few results on bigΘ…

Theorem: If we have two functions \(f_1(x)\) which is \(\Theta(g_1(x))\) and \(f_2(x)\) which is \(\Theta(g_2(x))\), and \(g_2(x)\) is \(O(g_1(x))\), then \(f_1(x)+f_2(x)\) is \(\Theta(g_1(x)))\).
 That is, when adding two functions together, the bigger one “wins”.

Theorem: If we have two functions \(f_1(x)\) which is \(\Theta(g(x))\) and \(f_2(x)\) which is \(O(g(x))\), then \(f(x)+g(x)\) is \(\Theta(g(x)))\).

Theorem: for a positive constant \(a\), a function \(af(x)\) is \(\Theta(g(x))\) iff \(f(x)\) is \(\Theta(g(x))\).
 That is, leading constants don't matter.

Corollary: Any degree\(n\) polynomial, \(f(x)=a_nx^n + a_{n1}x^{n1}+\cdots + a_1x+a_0\) with \(a_n\gt 0\) is in \(\Theta(x^n)\).

 What functions have a “higher” bigΘ than others is usually fairly obvious from a graph, but “I looked at a graph” isn't very much of a proof.
 The bigO notation sets up a hierarchy of function growth rates. Here are some of the important “categories”:
\[n!\\2^n\\n^3\\n^2\\n\log n\\n\\\sqrt{n}=n^{1/2}\\\log n\\1\]
 Each function here is bigO of ones above it, but not below.
 e.g. \(n\log n\) is \(O(n^2)\), but \(n^2\) is not \(O(n\log n)\).
 So in some important way, \(n^2\) grows faster than \(n\log n\).
 Where we are headed: we will be able to look at an algorithm and say that one that takes \(O(n\log n)\) steps is faster than one that takes \(O(n^2)\) steps (for large input).
Growth of Logarithms
 A note about logarithm functions and bigO/Ω/Θ…
 You will often see statements like “the function is \(O(\log n)\)” or “is \(\Theta(n\log n)\)” with no base mentioned.
 Remember this fact about logarithms: \[\log_b x = \frac{\log_a x}{\log_a b} = \frac{1}{\log_a b}\log_a x \,.\]
 That is, changing the base changes the value by a constant factor.
 Since constant factors don't change the bigO/Ω/Θ category, we don't care which base.
 \(f(x)\) is \(\Theta(log_a x)\) iff \(f(x)\) is \(\Theta(log_b x)\).
 So we'll often get lazy and not bother writing the base.