Big O
Fully Explained in Detail w/ Step-by-Step Examples!

It’s always better to be prepared than to be caught unawares.

And that preparation is critical regarding how much time and space are needed to run a program.

So, how do we ensure an algorithm runs efficiently and reliably?

By applying asymptotic analysis such as:

• Big-O
• Big-Omega
• Big-Theta

These notations are the best way to estimate a function’s growth for large input values.

Let’s take a closer look at each estimation.

Big-O (Big-Oh) Notation

Big O is the upper bound for the growth of a function and predicts the worst-case scenario.

Definition: If \(f\) and \(g\) are functions from the set of integers or real numbers to the set of real numbers. We say \(f(x)\) is big-O of g(x), denoted \(f(x)\) is O(g(x)), if \(g\) asymptotically dominates \(f\) and if there are witnesses \(C\) and \(k\), which are positive constants, such that:

\begin{equation}
|f(x)| \leq C|g(x)| \text { when } x>k
\end{equation}

What is important to note is that \(k\) is the point for which \(f(x)\) is bounded above by \(C g(x)\) for some wisely chosen constant multiplier \(C\).

Big-\(\Omega \) (Omega) Notation

Big-\(\Omega \) (Omega) is considered the lower bound and indicates the best-case scenario.

Definition: If \(f\) and \(g\) are functions from the set of integers or real numbers to the set of real numbers. We say \(f(x)\) is big-Omega of g(x), denoted \(f(x)\) is \(\Omega \left( {g\left( x \right)} \right)\), if there are witness \(C\) and \(k\), which are positive constants, such that:

\begin{equation}
|f(x)| \geq C|g(x)| \text { when } x>k
\end{equation}

So, \(k\) is the point for which \(f(x)\) is bounded below by \(Cg\left( x \right)\) for some astutely chosen constant multiplier \(C\).

Big-\(\Theta \) (Theta) Notation

Big-\(\Theta \) (Theta) is considered the tight-bound, similar to guardrails for our function.

Definition: If \(f\) and \(g\) are functions from the set of integers or real numbers to the set of real numbers. We say \(f(x)\) is big-Theta of g(x), denoted \(f(x)\) is \(\Theta \left( {g\left( x \right)} \right)\), if \(f(x)\) is O(g(x)) and \(f(x)\) is \(\Omega \left( {g\left( x \right)} \right)\). Such that:

\begin{equation}
c_1|g(x)| \leq f(x) \leq c_2|g(x)| \text { when } x>k
\end{equation}

when \(x>k\) for positive constants \({c_1}\), \({c_2}\), and \(k\).

In our previous lesson, we learned how to successfully identify whether a function is big-O (upper bound), big-omega (lower bound), or big-theta (tight bound) using the Asymptotic Limit Theorem.

Now, it’s up to us to sagely choose our witnesses, or positive constants \(c\) and \(k\), that prove \(f(x)\) is \(\Theta \left( {g\left( x \right)} \right)\),\(\Omega \left( {g\left( x \right)} \right)\) or both (i.e., \(\Theta \left( {g\left( x \right)} \right)\)).

How To Prove \(\Theta \left( {g\left( x \right)} \right)\),\(\Omega \left( {g\left( x \right)} \right)\) or \(\Theta \left( {g\left( x \right)} \right)\)

1. Use the Asymptotic limit Theorem to determine the growth of a function for large input values:
• \(\mathop {\lim }\limits_{n \to \infty } \left( {\frac{{f\left( x \right)}}{{g\left( x \right)}}} \right) = 0\) , then \(f\left( x \right)\) is \(O\left( {g\left( x \right)} \right)\) (Big-O)
• \(\mathop {\lim }\limits_{n \to \infty } \left( {\frac{{f\left( x \right)}}{{g\left( x \right)}}} \right) = \infty \) , then \(f(x)\) is \(\Omega \left( {g\left( x \right)} \right)\) (Big-Omega)
• \(\mathop {\lim }\limits_{n \to \infty } \left( {\frac{{f\left( x \right)}}{{g\left( x \right)}}} \right) = L\) , where \(0<L<\infty \), then \(f\left( x \right)\) is \(\Theta \left( {g\left( x \right)} \right)\) (Big-Theta)
2. If \(f\left( x \right) = O\left( {g\left( x \right)} \right)\), then
• Choose \(k=1\) and assume \(x>k\)
• Let \(\frac{{f\left( x \right)}}{{g\left( x \right)}} \le C\frac{{g\left( x \right)}}{{g\left( x \right)}} = C\) , showing \(\left| {f\left( x \right)} \right| \le C\left| {g\left( x \right)} \right|\) when \(x>k\)
• Adjust \(k\) if necessary
3. If \(f\left( x \right) = \Omega \left( {g\left( x \right)} \right)\), then
• Assume \(x>k\)
• Show \(\left| {f\left( x \right)} \right| \ge C\left| {g\left( x \right)} \right|\) by choosing (guessing) a constant \(C\) that makes the inequality true
• Adjust \(k\) if necessary
4. If \(f\left( x \right) = \Theta \left( {g\left( x \right)} \right)\):
• Show \(f\left( x \right) = O\left( {g\left( x \right)} \right)\) using the steps above
• Show \(f\left( x \right) = \Omega \left( {g\left( x \right)} \right)\)using the steps above
• Note that the constants \(c\) and \(k\) may be different for \(O(g(x))\) and \(\Omega(g(x))\)

Key Insight

And after teaching this material for years, there is something vital you must keep in mind…

…there is no perfect or unique choice of \(c\) and \(k\), so answers will vary from person to person.

Depending on our choices, we can increase \(c\) or \(k\), or both, as we only need to show that a pair of constants exist.

Example

Let’s look at a practice problem to better understand what is happening.

Question: Suppose we are asked to determine whether \(f\left( x \right) = 4x + 17\) is \(O\left( x \right),\;\Omega \left( x \right),\;or\;\Theta \left( x \right)\) and find appropriate witnesses \(c\) and \(k\).

Answer:

Step 1:

First, we use our Asymptotic Limit Theorem to determine which growth of a function we are dealing with:

\begin{equation}
\begin{aligned}
&\lim _{n \rightarrow \infty}\left(\frac{f(x)}{g(x)}\right) \\
&\lim _{n \rightarrow \infty}\left(\frac{4 x+17}{x}\right)=\frac{4}{1}=4
\end{aligned}
\end{equation}

And since \(0<4<\infty \) this means that our function, \(f\left( x \right) = 4x + 17\) is \(\Theta \left( x \right)\) Big-Theta of x.

So, now that we know \(f\left( x \right)\) is big Theta of \(g\left( x \right)\) we now need to show that \(f\left( x \right)\) is both Big-O of \(g\left( x \right)\) and Big-Omega of \(g\left( x \right)\) by finding respective constants \(c\) and \(k\).

Step 2:

Let’s start with Big-O.

We can find our witnesses in several ways, and each is perfectly acceptable.

Option 1:

One option is to replace every term of \(f\left( x \right)\) with \(g\left( x \right)\), as seen below
\[\begin{array}{*{20}{c}}
{f\left( x \right)}& = &{4x + 17}\\
{}& \le &{4x + 17x}\\
{}& = &{21x}
\end{array},when\;x \ge 1\]

Therefore, \(f\left( x \right) = O\left( x \right)\) when \(c = 21\) and \(k = 1\).

And this can be shown to be valid, as the graph of \(f\left( x \right) = 4x + 17\) is entirely bounded above by the graph of \(g\left( x \right) = 21x\), when \(x>1\).

Option 2:

But a second option is to replace any constant terms with an additional \(g\left( x \right)\) term, as seen here:
\[\begin{array}{*{20}{c}}
{f\left( x \right)}& = &{4x + 17}\\
{}& \le &{4x + x}\\
{}& = &{5x}
\end{array},when\;x \ge 17\]

Therefore, \(f\left( x \right) = O\left( x \right)\) when \(c = 5\) and \(k = 17\). Notice that in doing so, we merely started our “breakpoint” for \(k\) to begin at the constant term.

And, once again, this can be shown to be valid, as the graph of \(f\left( x \right) = 4x + 17\) is entirely bounded above by the graph of \(g\left( x \right) = 5x\), when \(x>17\).

We can find suitable constants in many ways, but the most important is finding a pair of witnesses that satisfy the definition.

Step 3:

Now, we must focus on proving Big Omega for our function.

Here, we start by assuming \(k = 1\) and then choosing (guessing) a suitable constant, \(c\).

\[\begin{array}{*{20}{c}}
{\left| {f\left( x \right)} \right|}& \ge &{c\left| {g\left( x \right)} \right|}\\
{\left| {4x + 17} \right|}& \ge &{c\left| x \right|}\\
{4x + 17}& \ge &{\frac{1}{2}x}
\end{array},\;let\;c = \frac{1}{2}\]

Therefore, \(f(x)=\Omega(x)\) when \(c=\frac{1}{2}\) and \(k=1\).

If we were to graph \(f(x)=4 x+17\) and \(g(x)=\frac{1}{2} x\) we would easily notice that \(f(x)\) is entirely bounded below by \(g(x)\), thus showing our constants to be suitable.

But once again, many possible answers could also suffice, but the point is that we need to find one pair that satisfies the definition, which we did.

Summary

Don’t worry. All will become clear after watching the video, as we will work through countless examples together and learn how to find suitable constants that prove big-O, big-Omega, and big-Theta.

Let’s jump right in.

Video Tutorial w/ Full Lesson & Detailed Examples

Get access to all the courses and over 450 HD videos with your subscription

Monthly and Yearly Plans Available

Get My Subscription Now

Still wondering if CalcWorkshop is right for you?
Take a Tour and find out how a membership can take the struggle out of learning math.