Main content

# Big-O notation

We use big-Θ notation to asymptotically bound the growth of a running time to within constant factors above and below. Sometimes we want to bound from only above.

For example, although the worst-case running time of binary search is $\mathrm{\Theta}({\mathrm{log}}_{2}n)$ , it would be incorrect to say that binary search runs in $\mathrm{\Theta}({\mathrm{log}}_{2}n)$ time in $\mathrm{\Theta}(1)$ time. The running time of binary search is never worse than $\mathrm{\Theta}({\mathrm{log}}_{2}n)$ , but it's sometimes better.

*all*cases. What if we find the target value upon the first guess? Then it runs inIt would be convenient to have a form of asymptotic notation that means "the running time grows at most this much, but it could grow more slowly." We use "big-O" notation for just such occasions.

If a running time is $O(f(n))$ , then for large enough $n$ , the running time is at most $k\cdot f(n)$ for some constant $k$ . Here's how to think of a running time that is $O(f(n))$ :

We say that the running time is "big-O of $f(n)$ " or just "O of $f(n)$ ." We use big-O notation for

**asymptotic upper bounds**, since it bounds the growth of the running time from above for large enough input sizes.Now we have a way to characterize the running time of binary search in all cases. We can say that the running time of binary search is $O({\mathrm{log}}_{2}n)$ . We can make a stronger statement about the worst-case running time: it's $\mathrm{\Theta}({\mathrm{log}}_{2}n)$ . But for a blanket statement that covers all cases, the strongest statement we can make is that binary search runs in $O({\mathrm{log}}_{2}n)$ time.

*always*If you go back to the definition of big-Θ notation, you'll notice that it looks a lot like big-O notation, except that big-Θ notation bounds the running time from both above and below, rather than just from above. If we say that a running time is $\mathrm{\Theta}(f(n))$ in a particular situation, then it's also $O(f(n))$ . For example, we can say that because the worst-case running time of binary search is $\mathrm{\Theta}({\mathrm{log}}_{2}n)$ , it's also $O({\mathrm{log}}_{2}n)$ .

The converse is not necessarily true: as we've seen, we can say that binary search always runs in $O({\mathrm{log}}_{2}n)$ time but $\mathrm{\Theta}({\mathrm{log}}_{2}n)$ time.

*not*that it always runs inBecause big-O notation gives only an asymptotic upper bound, and not an asymptotically tight bound, we can make statements that at first glance seem incorrect, but are technically correct. For example, it is absolutely correct to say that binary search runs in $O(n)$ time. That's because the running time grows no faster than a constant times $n$ . In fact, it grows slower.

Think of it this way. Suppose you have 10 dollars in your pocket. You go up to your friend and say, "I have an amount of money in my pocket, and I guarantee that it's no more than one million dollars." Your statement is absolutely true, though not terribly precise.

One million dollars is an upper bound on 10 dollars, just as $O(n)$ is an upper bound on the running time of binary search. Other, imprecise, upper bounds on binary search would be $O({n}^{2})$ , $O({n}^{3})$ , and $O({2}^{n})$ . But none of $\mathrm{\Theta}(n)$ , $\mathrm{\Theta}({n}^{2})$ , $\mathrm{\Theta}({n}^{3})$ , and $\mathrm{\Theta}({2}^{n})$ would be correct to describe the running time of binary search in any case.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

## Want to join the conversation?

- I didn't understand this sentence: "Other, imprecise, upper bounds on binary search would be O(n^2), O(n^3), and O(2^n). But none of Θ(n),Θ (n^2), Θ(n^3), and Θ (2^n)would be correct to describe the running time of binary search in any case."

Can someone explain it to me please? Thank you!(26 votes)- Here's a couple definitions to keep in mind:

if f(n) is O(g(n)) this means that f(n) grows asymptotically no faster than g(n)

if f(n) is Θ(g(n)) this means that f(n) grows asymptotically at the same rate as g(n)

Let's call the running time of binary search f(n).

f(n) is k * log(n) + c ( k and c are constants)

Asymptotically, log(n) grows no faster than log(n) (since it's the same), n, n^2, n^3 or 2^n.

So we can say f(n) is O(log(n)), O(n), O(n^2), O(n^3), and O(2^n).

This is similar to having x = 1, and saying x <= 1, x <= 10, x <= 100, x <= 1000, x <= 1000000.

All of these statements are true, but the most precise statement is x <= 1. By precise, we mean that it gives us the best idea of what x actually is.

Asymptotically, log(n) grows at the same rate as log(n) (since it is the same).

So, we can say that f(n) is Θ( log(n) )

This would be similar to having x=1 and then saying x = 1, which would be a precise statement that tells us what x is.

However, asymptotically, log(n) grows slower than n, n^2, n^3 or 2^n i.e. log(n) does not grow at the same rate as these functions.

So, we can not say f(n) is Θ(n), Θ(n^2), Θ(n^3), and Θ(2^n).

Similarly if x = 1, we can not say that x = 10, x = 100, x = 1000, or x = 1000000.

Hope this makes sense(139 votes)

- If I'm not mistaken, the first paragraph is a bit misleading.

Before, we used big-Theta notation to describe the*worst case*running time of binary search, which*is*Θ(lg n). The*best case*running time is a completely different matter, and it is Θ(1).

That is, there are (at least) three different types of running times that we generally consider: best case, average/expected case, and worst case. Usually it's the latter two that are the most useful. For binary search, the best case time is Θ(1), and the expected and worst case times are Θ(lg n).(30 votes) - The complexity of this article is (n^3) at least(30 votes)
- What is upper bound, lower bound and tight bound ?(6 votes)

- And I thought I could do this. :( Cant learn everything.(7 votes)
- If you think you can't, you're right. If you think you can you're also right. It's all in how you think about it. Stick for awhile till the function storm passes, it'll surprise you how you don't even really need to know the math, just how fast some few functions growth because you have to compare the rate of growth of algorithms to them. Like knowing the order the alphabets come so you know where to place a stray alphabet.(37 votes)

- I really don't get this paragraph, could someone please explain it to me in other words?? Thank you!

"Now we have a way to characterize the running time of binary search in all cases. We can say that the running time of binary search is always O(\lg n)O(lgn). We can make a stronger statement about the worst-case running time: it's \Theta(\lg n)Θ(lgn). But for a blanket statement that covers all cases, the strongest statement we can make is that binary search runs in O(\lg n)O(lgn) time."(4 votes)- It means that:

- You can find a scenario when binary search takes Tetha(lg n).

- Ignoring worst case scenario, binary search will generally take Big-O(lg n) time. Because not all of the binary search runs will take Tetha(lg n).(3 votes)

- I didn't understand this: " If we say that a running time is Θ(f(n)) in a particular situation, then it's also O(f(n)). "

Binary search is Θ(1) in a particular situation (best case) but it is not O(1).(3 votes)- It looks like you are confusing O and Ω with worst case and best case. They are not the same. First we specify the case (worst,best, average, etc.) and then we specify O, Ω (upper bound, lower bound) or Θ (tight bounds).

For Binary search:

In the best case scenario (our initial guess finds the target value):

- binary search is Θ(1) and as a result is also Ω(1) and O(1).

In the worst case scenario (our target is not in the array)

-binary search is Θ( log n) and as a result is also Ω( log n) and O( log n).(11 votes)

- I have a question on upper ane lower bounds to make sure my understanding is spot on. Please tell me if I am correct or not and why if not. Given the set S = {2, 3, 5, 7, 9, 12, 17, 42} A lower bound could be 2 or 3 for examaple but in set S only 2 is the tight lower bound and only 42 is the tight upper bound. Is this correct?(2 votes)
- A lower bound has to be less than or equal to all members of the set. Therefore, here 3 is not a lower bound because it is greater than a member of the set (2). 1 is a lower bound, -3592 is a lower bound, 1.999 is a lower bound -- because each of those is less than every member of the set.

There is always only 1 tight lower bound: the greatest of all the lower bounds. Here, 2 is indeed the tight lower bound.

Similarly, there is always only 1 tight upper bound: the least of all the upper bounds. Here, 42 is indeed the tight upper bound.

Try this example:

Given the set S2 = {-12, -5, 0, 1, 3, 3}, what is a lower bound? What is an upper bound?(12 votes)

- Is it absolutely correct to say that binary search runs in Big-O(n)?Why couldn't we say it can run in Big-O(n^2).SInce the upperbound for binary search is Big-O(log(n)) do you mean to say that we start from n and then go to n^2 for considering upperbound of an algorithm.For example if an algorithm runs in Big-Theta(n) can we say it runs in Big-O(n^2)?(3 votes)
- Binary search is Θ(log n) which means that it is O(log n) and Ω(log n)

Since binary search is O(log n) it is also O(any function larger than log n)

i.e. binary search is O(n), O(n^2), O(n^3), O(e^n), O(n!), etc,

Another way to express this is by saying:

Binary search doesn't run slower than really fast algorithms ( O(log n) ), so:

Binary search doesn't run slower than fast algorithms ( O(n) ) , so:

Binary search doesn't run slower than moderate to slow algorithms ( O(n^2), O(n^3) ), so:

Binary search doesn't run slower than horribly slow algorithms ( O(e^n), O(n!) )

Hope this make sense(6 votes)

- These two statements seem contradictory. Earlier, the article says that the running time of binary search is always Olog(n) [Para. 6]. Then it says the running time of binary search is O(n) [Para. 3 from bottom].

I've been taught that the running time of binary search is O log(n) while linear search is O(n). Confusing!(3 votes) - So, very basicly: Big O notation doesn't need to be precise as long as its still over the running time. In contrast, Big-Theta notation need to be precise as it is describing the running time itself.

Is that right?(2 votes)- Both Big O and Big Theta are descriptions of the running time function. Big O describes the upper bound of the running time function. Big Theta describes where the upper and lower bounds of the running time function meet.

While Big O**can technically**be anything over the running time,**in practice**, we want it to be as tight to the running time as possible. If you had an algorithm with a running time that was known to be Big O n^2 and you said it was Big O n^3 (which is technically true), people would probably try to correct you and say it is Big O n^2 (which is a better description of the running time function, because it bounds it more tightly).

Big Theta is a more precise description of the running time function in the sense that it is where the lower bounds and upper bounds meet (it gives you the assurance that the lower bound isn't any higher, and the upper bound isn't any lower). But a Big Theta n^2 includes both 0.0001 n^2 and 999999999 n^2 + 5000000, so it isn't necessarily what one would call a "precise" description.(5 votes)