3
$\begingroup$

I'm given the runtimes for input size $n=100$ of some polynomial-time (big-Oh) algorithms and an $\mathcal{O}(n \log(n))$ one. I want to calculate the runtimes for: $200$, $1000$ and $10000$.

For the polynomials it is trivial. The results I should get for the $n \log n$ case are: $0.06$, $1$ and $20$ seconds respectively, where $0.03s$ was given for $n=100$.

I have tried: (examples should have $0.06$ as solution)

(1) $\frac{f(2x)}{f(x)}$ similarly to how I've got the right solution to the polynomials, $\frac{2x \log(2x)}{x \log x} = \ldots= 2 \log((2x)^{1/\log x})$, not getting anywhere, and substituting $n=100$ gives $2.3010$ for any $\log$ base.

(2) calculating the "unit time of execution" $x$, from $100 x \log(100x)=0.03$ after approximating the inverse of $y=n \log n$ for $y=0.03$, $n=1.03$ for natural $\log$, substitution gives: $1.48$. $n=1.02058$ for binary $\log$, substitution gives: $2.10$

(3) calculating "unit time of execution" from the polynomial cases, which yield different for each, and result in negative runtimes predictions for the nlogn algorithm

(?) I also thought of searching for a function that is $\mathcal{O}(n \log n)$ and fits onto the points given by the solution, but thats over my head.

How to get to the solution ? Did any of my attempts made sense ?

  • 0
    Thanks for the detailed answer. It probably just trying to emphasize the orders of growth, because it is a first assignment about computational complexity and big-Oh. But not knowing how the answer for that one case came along keeps bugging me, and I can't step over it for days now. Because it is a free online course, I can't just ask the TA. Do you think that one column of the solution is simply wrong ? (section assignment 5, last problem from http://see.stanford.edu/see/materials/icspacs106b/assignments.aspx)2011-12-22
  • 0
    (I think this was supposed to be a comment to my answer, rather than a separate answer). Based on this new information, I'm quite certain that the solution set is simply wrong. I can see no justification for the numbers they give, much less any reason why a student would be expected to arrive at _those_ numbers in particular. Next time please add such links to the source of the problem to the question itself; that makes it much easier to figure out which kind of answer would be useful.2011-12-22
  • 0
    @nlognfan: your accounts have been merged. Please register your account to avoid creating duplicate accounts in the future.2011-12-23

1 Answers 1