0
$\begingroup$

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)

  • 0
    Presumably, these logs are base 2.2012-03-09

1 Answers 1

2

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.