Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
Presumably, these logs are base 2. –  Gerry Myerson Mar 9 '12 at 11:58
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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