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

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

Jenn (B.S., M.Ed.) of Calcworkshop® teaching big o

Jenn, Founder Calcworkshop^®, 15+ Years Experience (Licensed & Certified Teacher)

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:

$| f (x) | \leq C | g (x) | when x > k$

Big Oh – Upper Bound Graph

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) Notation

Big- $Ω$ (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 $Ω (g (x))$ , if there are witness $C$ and $k$ , which are positive constants, such that:

$| f (x) | \geq C | g (x) | when x > k$

Big Omega – Lower Bound Graph

So, $k$ is the point for which $f (x)$ is bounded below by $C g (x)$ for some astutely chosen constant multiplier $C$ .

Big- $Θ$ (Theta) Notation

Big- $Θ$ (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 $Θ (g (x))$ , if $f (x)$ is O(g(x)) and $f (x)$ is $Ω (g (x))$ . Such that:

$c_{1} | g (x) | \leq f (x) \leq c_{2} | g (x) | when x > k$

when $x > k$ for positive constants $c_{1}$ , $c_{2}$ , and $k$ .

Big Theta – Tight Bound Graph

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 $Θ (g (x))$ , $Ω (g (x))$ or both (i.e., $Θ (g (x))$ ).

How To Prove $Θ (g (x))$ , $Ω (g (x))$ or $Θ (g (x))$

Use the Asymptotic limit Theorem to determine the growth of a function for large input values:

$lim_{n \to \infty} (\frac{f (x)}{g (x)}) = 0$ , then $f (x)$ is $O (g (x))$ (Big-O)
$lim_{n \to \infty} (\frac{f (x)}{g (x)}) = \infty$ , then $f (x)$ is $Ω (g (x))$ (Big-Omega)
$lim_{n \to \infty} (\frac{f (x)}{g (x)}) = L$ , where $0 < L < \infty$ , then $f (x)$ is $Θ (g (x))$ (Big-Theta)

If $f (x) = O (g (x))$ , then

Choose $k = 1$ and assume $x > k$
Let $\frac{f (x)}{g (x)} \leq C \frac{g (x)}{g (x)} = C$ , showing $| f (x) | \leq C | g (x) |$ when $x > k$
Adjust $k$ if necessary

If $f (x) = Ω (g (x))$ , then

Assume $x > k$
Show $| f (x) | \geq C | g (x) |$ by choosing (guessing) a constant $C$ that makes the inequality true
Adjust $k$ if necessary

If $f (x) = Θ (g (x))$ :

Show $f (x) = O (g (x))$ using the steps above
Show $f (x) = Ω (g (x))$ using the steps above
Note that the constants $c$ and $k$ may be different for $O (g (x))$ and $Ω (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 (x) = 4 x + 17$ is $O (x), Ω (x), o r Θ (x)$ 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{aligned} lim_{n \to \infty} (\frac{f (x)}{g (x)}) \\ lim_{n \to \infty} (\frac{4 x + 17}{x}) = \frac{4}{1} = 4 \end{aligned}$

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

So, now that we know $f (x)$ is big Theta of $g (x)$ we now need to show that $f (x)$ is both Big-O of $g (x)$ and Big-Omega of $g (x)$ 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 (x)$ with $g (x)$ , as seen below
$\begin{matrix} f (x) & = & 4 x + 17 \\ \leq & 4 x + 17 x \\ = & 21 x \end{matrix}, w h e n x \geq 1$

Therefore, $f (x) = O (x)$ when $c = 21$ and $k = 1$ .

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

Option 2:

But a second option is to replace any constant terms with an additional $g (x)$ term, as seen here:
$\begin{matrix} f (x) & = & 4 x + 17 \\ \leq & 4 x + x \\ = & 5 x \end{matrix}, w h e n x \geq 17$

Therefore, $f (x) = O (x)$ 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 (x) = 4 x + 17$ is entirely bounded above by the graph of $g (x) = 5 x$ , 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{matrix} | f (x) | & \geq & c | g (x) | \\ | 4 x + 17 | & \geq & c | x | \\ 4 x + 17 & \geq & \frac{1}{2} x \end{matrix}, l e t c = \frac{1}{2}$

Therefore, $f (x) = Ω (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

calcworkshop jenn teaching big o

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.

4.9 / 5

1,128 Reviews

Kevin S.10-30-24 - CO, United States

I had never even heard of discrete math before I had to take it for my Bachelor's in Cybersecurity. I had actually hoped that my math days were done! I suffered through class not understanding any of the presentations until I stumbled across Calcworkshop. I used the Calcworkshop lessons more than I used my instructor's lectures and my book. I ended up with a high B (just 12 points away from an A) thanks to Jenn. Without her easy to understand style of teaching, I'm not sure I would have even passed the class. Thank you so much!!!

Richard10-29-24 - Norway

Very well structured and site. It is well structured giving a good overview of the different topics regarding all mathematics where you easily can choose which path is applicable to your specific needs.The video lectures are superb with introduction to the topic followed by a detailed theoretically explaination and what I personally get most out of is; heaps of examples where you are taken and shown, step by step, the prosess of solving the problem. They also includd practice sheets and solutions to test yourself after each chapter. There is a lot to undertake on this site, but it provides an easy and understandable interface to map out what you need to do. The site has been very helpfull for me and I highly recommend it.

RobWP10-26-24 - United States

I am taking this course for mainly linear algebra review. It is a course that I have had but fairly long ago. I'm currently working in masters in data science and linear algebra namely transformations is something that has come up and I thought I need a good review on. I so far what I have liked about the course is, the common sense approach. Her approach makes it easy to remember the concepts because of her common sense approach. I like the fact that she gives information that is not really in any textbooks. I can vouch for that because not only have I used textbook recently to review I have had a formal class in the past that used textbooks. She goes over things thoroughly and for the price it's very much worth it. I have had many quarters of formal calculus and differential equations courses and I am kind of anxious to look to see what her approach to calculus is. I can't really answer how this class would be for a novice or someone who has not had linear algebra the past, but I really don't think they need to worry about that. Her method I feel will make a novice be successful and to understand the material. She is very easy to understand. Gives good examples but doesn't beat a dead horse either. What I like about her introductory remarks is that she says what linear algebra is all about and she points out what the core of the linear algebra is about and what you need to know. Having taken it before I would have to agree and she is dead on spot.

Robbin03-18-25 - CO, United States

Very well organized, helpful and comprehensive. It is great also to have access to prior course material so you can easily go back and refresh if you need to. Jenn is very clear and the number of examples leaves one comfortable with each topic. Couldn't be happier.

RCJK03-07-25 - ID, United States

I had to take Calculus I and II as accelerated classes while working full time. It was my first time taking this courses and was very overwhelming. Calcworkshop really made learning the subjects easier for me by having all the subjects easy to find and easy to understand explanations. I received a B in both classes which I am extremely happy with doing the classes in double time.

Jacqueline S.03-07-25 - SC, United States

Jenn is awesome!Her breakdown of the topic is beyond what you would expect. She is showing you how to arrive at the answer instead of doing a simple equation. Most people need to know the why it give confidence and structure to the learning process. This is what Jenn is great at, she knows how to deliver the information to a non math mind in a way that instills knowledge that you can forever draw from as you move forward. It's really well thought out. She is a true master teacher. Thanks for all that you do for us! Hugs n Blessings... JS

Rose M.03-07-25 - CA, United States

Best instructor ever, I have never had Math explained in a way that was so interesting. Her lectures and instruction is explained perfectly, and I will continue to use this for all my future math courses.

A Reviewer03-07-25 - United States

I needed help with college precalculus, they provided more than enough help that allowed me to succeed and get the scores I needed.

Jujuana03-05-25 - MO, United States

I love the videos the way each lesson is explained step by step. I love that she has examples that you can go over again and again in order to understand the way algebra works. I was lost because my instructor was flying through each lesson and I was totally lost. I attached my syllabus and they helped me stay focus on what I was working and give me a guide to go back and refresh what I went over in class.

Stacey01-31-25 - AZ, United States

Hello, I highly recommend getting a subscription to Jenn and her Calcworkshop teaching math service. I did a general, "go from bad to good at math", Google search and found out about Calcworkshop through responses to the topic on reddit. I've just started watching her videos and found them to be extremely helpful. I'm going back to college after a long absence and math was never my strong suit. So I'm starting at the very bottom of her available subjects and going from there. Just watching a couple of the videos has taken me from being dragged along not understanding to following along just fine in my math class. I'm moving from the "I'll never get this", to the "I look forward to understanding this", mindset in approaching math. This for me is huge, and even though I have a long way to go, I'm confident I will get there thanks to Jenn. Totally worth it!

Kathy W.01-14-25 - WA, United States

Calcworkshop is an outstanding source to learn math and understanding math concepts. Jenn is an outstanding master teacher. Every lesson is clearly presented making understanding easy to grasp. Practice lessons with accompanying answers are given for each section. I am 82, a retired teacher and lifelong learner. Learning calculus has always been on my bucket list. Calcworkshop is helping me reach my goal.

Cheryl01-14-25 - NY, United States

Calc workshop is the absolutely best resource for math and I have seen almost everything that exists out there. I have even recommended it to my daughter's school so that all the kids could use the videos during the summer months for the subject they plan to study in the fall. They are guaranteed to get a A if they have watched the videos and completed the problems before taking the class. Students who are weak in areas can access lower level classes and those who seek to advance above grade level can do so. The videos and exercises are crystal clear and the excellent presentations raise the bar for teachers everywhere. I have always believed that one great math teacher is important in the education process. The videos, exercises and problems are excellent. It is not possible to have ANY knowledge gaps. I have never seen anything on the market that even begins to compete with it!

Justin N.12-22-24 - OK, United States

Calculus can be a scary subject. I know I was scared. I had been out of any math class for over 23 years. I had taken an 8 week Calculus 1 class and felt like I was overloaded. Going into Calculus 2 I found CALCWORKSHOP.com. I used the training videos and material to really dive back into Calc 1 and prepare for Calc 2. Long story short with the material provided and ample study time, I finished Calc 2 with a 95%. Thanks Jenn!

Shelby12-10-24 - OH, United States

CalcWorkshop was a wonderful resource as someone going onto a college calculus 1 class after not having taken a math course in a year! Jenn always explained things in a logical order that built upon previous lessons, and the way she explained topics was always easy to understand. Calcworkshop saved this semester for me, and I couldn't be more grateful to have found this site. :)

Jordan Q.12-09-24 - AR, United States

Anyone struggling with math at any level would greatly benefit from this product. I signed up for it immediately after getting a D on my first exam in calculus 2 and ended up getting A's and B's on the remaining exams, getting a B overall in the class. Jenn breaks down the topics, without skipping any steps, in a way that makes them very easy to understand. I highly recommend this product!

N8Booker11-28-24 - MA, United States

I'm in school to get my degree Networking and Cybersecurity and I'm in my first year. I've been away from school for quite a long time so the concepts that are being taught although not foreign to me, have so much dust on them from a lack of being used in real world applications regularly.I stumbled upon CalcWorkshop by pure chance and it has been a game changer for me. Jen filled in the gaps in between what my Professor is teaching at a rapid fire pace and where my brain grasps and applies it. If not for Jen's approach, I'd have failed my test I took miserably!Am I grateful? It goes beyond words and not I recommend her workshops to everyone!

Kevin S.10-30-24 - CO, United States

Richard10-29-24 - Norway

RobWP10-26-24 - United States

RCJK03-07-25 - ID, United States

Jacqueline S.03-07-25 - SC, United States

See more reviews on Shopper Approved

Big-O (Big-Oh) Notation

Big-Ω (Omega) Notation

Big-Θ (Theta) Notation

How To Prove Θ(g(x)),Ω(g(x)) or Θ(g(x))

Key Insight

Example

Step 1:

Step 2:

Option 1:

Option 2:

Step 3:

Summary

Video Tutorial w/ Full Lesson & Detailed Examples

Big- $Ω$ (Omega) Notation

Big- $Θ$ (Theta) Notation

How To Prove $Θ (g (x))$ , $Ω (g (x))$ or $Θ (g (x))$