Estimating With Big-O

Section 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:

🔗

\begin{matrix} \frac{work for job 1}{work for job 2} = \frac{time for job 1}{time for job 2} \end{matrix}

🔗

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 (l o g_{2} (n)) .$ That means the estimated work would be $l o 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 8.14.1.

You can use the Wolfram Alpha website

http://www.wolframalpha.com/

to calculate log base 2 by typing something like “log2(1024)”. Try it below.

🔗

Example 8.14.2. 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:

🔗

\begin{matrix} \frac{10000^{2}}{50000^{2}} = \frac{0.243 seconds}{time for job 2} \end{matrix}

🔗

So…

🔗

\begin{matrix} \frac{100000000}{2500000000} = \frac{0.243 seconds}{time for job 2} \end{matrix}

🔗

Cross multiplying gives:

🔗

\begin{matrix} 100000000 (time for job 2) = 0.243 seconds \cdot 2500000000 \end{matrix}

🔗

Solving for time for job 2 gives:

🔗

\begin{matrix} time for job 2 = 6.075 seconds \end{matrix}

🔗

Example 8.14.3. Sample problem 2.

I have timed a 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