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:
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.
If we want to do a Binary Search, the Big-O is \(O(log_2(n))\text{.}\) That means the estimated work would be \(log_2(1000)\) or ~9.9657 units of work.
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:
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 \(O(n)\) algorithm, so the work for job 1 will be 10,000,000. For job 2, we are using a \(O(log_2(n))\) algorithm so the work will be \(log_2(10000000)\)
\begin{gather*}
\frac{10000000}{log_2(10000000)} = \frac{8.12\textrm{ seconds}}{\textrm{time for job 2}}
\end{gather*}