Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am reviewing BigO notation from this document:

This document contains this information and the accompanying table:

In the following table we suppose that a linear algorithm can do a problem up to size 1000 in 1 second. We then use this to calculate how large a problem this algorithm could handle in 1 minute and 1 hour.

Algorithm Problem Sizes

I can see where values such as $n^2$ come from, as it is getting the square root of 1000. However, I am at a loss as to how the author calculated $2^n$ and $n log(n)$. Could someone help determine how these values are calculated?

share|cite|improve this question
up vote 2 down vote accepted

For $2^n$, you just take the logarithm to the base $2$.

For $n\log n$, you are looking for the largest integer $n$ such that $n\log n$ does not exceed, say, $1000$. You can do that by just trying different values of $n$, zeroing in on the right value; there are more systematic ways, such as Newton's Method --- someone just asked a question here about solving $n\log n\le1,000,000$, maybe you could dig up that question and see what's written there.

share|cite|improve this answer
Thanks! Logs are a tricky thing for me. Now to see if I can find that other question. – MrX Jun 2 '13 at 6:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.