Suppose you have a program that solves an AI problem. When the problem size is $N = 1,000$ your program takes 10 seconds to find a solution. Estimate the time it will take to solve a problem of size $N = 1,000,000$ if the time complexity of your algorithm is:

  1. $\mathcal{O}(\log N)$

  2. $\mathcal{O}(N)$

  3. $\mathcal{O}(N\log N)$

  4. $\mathcal{O}(N^2)$

  5. $\mathcal{O}(N^3)$

You may use the approximations $\log(1,000) = 10$ and $\log(1,000,000) = 20$

(I'm not great at maths so I really do appreciate any help given)

  • $\begingroup$ Presumably, these logs are base 2. $\endgroup$ – Gerry Myerson Mar 9 '12 at 11:58

Let’s start with (4). The use of the $O$ notation here is very sloppy, but what is meant here by saying that the time complexity of the algorithm is $O(N^2)$ is that the time required is roughly proportional to $N^2$. That is, there is some constant $k$ such that the time required to process an input of size $N$ is approximately $kN^2$. In this problem you’re told that when $N=1000$, the time is $10$ seconds, so $k(1000)^2=10$. You could solve this for $k$, if you really wanted to, but it’s unnecessary: you want $kN^2$ when $N=1,000,000$, and $1,000,000=1000^2$, so you want $$k(1,000,000)^2= k(1000)^2(1000)^2=10(1000)^2=10,000,000\;,$$ since $k(1000)^2=10$. In other words, in (4) your algorithm will take about ten million seconds, which is a little less than a third of a year.

In (2) you’re told that the algorithm takes about $kN$ seconds to handle a problem of size $N$, and you know that $1000k=10$. I’ll let you try to solve this one and (5) using my solution to (4) as a model; you should get a little over two and three-quarters hours for (2) and over three centuries for (5).

Now let’s look at (1): it says that the approximate running time on an input of size $N$ is $k\log N$ for some constant $k$, and we’re told that $k\log 1000=10$. You’re allowed the approximation $\log 1000\approx 10$, so we have $10k=10$, or $k=1$. Thus, the approximate running time for $N=1,000,000$ is $$k\log 1,000,000=\log 1,000,000\approx 20$$ seconds.

(3) looks the messiest, but it’s no harder than the others: the approximate running time on an input of size $N$ is $kN\log N$, and you’re given that $k(1000)\log 1000=10$. Once again you can either solve for $k$ and plug in $N=1,000,000$ or use the given data point in a more direct way, as I did with (4); you should get a running time of a bit over five and a half hours.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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