8.14. Estimating With Big-O

We can use Big-O categories to do an estimation of how long a problem will take to solve based on a smaller version of the problem. We simply need to set up a proportion like the one below and solve it:

$\frac{\text{work for job 1}}{\text{work for job 2}}=\frac{\text{time for job 1}}{\text{time for job 2}}$

The key is to remember that the work does not necessarily equal the size of the problem. Instead, we have to use the size of the problem and the Big-O of the algorithm we are applying to calculate the approximate amount of work.

For example, say we have a list of 1000 things…

• If we want to do a Binary Search, the Big-O is $O(lo{g}_2(n))$. That means the estimated work would be $lo{g}_2(1000)$ or ~9.9657 units of work.

• If we want to do a Linear Search, the Big-O is $O(n)$. That means the estimated work would just be 1,000 units of work.

• If we want to do a Selection Sort, the Big-O is $O(n^2)$. That means the estimated work would be ${1000}^2$ or 1,000,000 units of work.

Note

You can use Wolfram Alpha website to calculate log base 2 by typing something like “log2(1024)”. Try it below.

Sample Problem 1

I have timed selection sort on 10,000 items and it takes 0.243 seconds. I want to estimate the time it will take to sort 50,000 items. Because selection sort is an $O(n^2)$ algorithm, I know I need to square the problem sizes to estimate the amount of work required for each of the two jobs. So I can set up the proportion like this:

$\frac{{10000}^2}{{50000}^2}=\frac{0.243\text{ seconds}}{\text{time for job 2}}$

So…

$\frac{100000000}{2500000000}=\frac{0.243\text{ seconds}}{\text{time for job 2}}$

Cross multiplying gives:

$100000000(\text{time for job 2})=0.243\text{ seconds}\cdot 2500000000$

Solving for time for job 2 gives:

$\text{time for job 2}=6.075\text{ seconds}$

Sample Problem 2

I have timed linear search on 10,000,000 items and it takes 8.12 seconds (call this job 1). I want to estimate the time it will take to use binary search instead (job 2). The problem sizes are the same for both jobs: 10,000,000 items. However, the algorithms will require different amounts of work. Linear search is a $O(n)$ algorithm, so the work for job 1 will be 10,000,000. For job 2, we are using a $O(lo{g}_2(n))$ algorithm so the work will be $lo{g}_2(10000000)$

$\frac{10000000}{lo{g}_2(10000000)}=\frac{8.12\text{ seconds}}{\text{time for job 2}}$

So…

$\frac{10000000}{23.25}=\frac{8.12\text{ seconds}}{\text{time for job 2}}$

Cross multiplying gives:

$10000000(\text{time for job 2})=8.12\text{ seconds}\cdot 23.25$

Solving for time for job 2 gives:

$\text{time for job 2}=0.000019\text{ seconds}$

Significantly faster!

You have attempted 1 of 1 activities on this page