3
$\begingroup$

Provide an algorithm computing performance $O (n^3 \log n)$. Your algorithm should contain only simple operations.

Any idea of how to approach this problem?...I am studying for the computer science GRE. Tanks!

$\endgroup$
6
  • $\begingroup$ @Amzoti yes...only that $\endgroup$ – computer scientist Aug 22 '13 at 5:38
  • 6
    $\begingroup$ Sort $n^2$ lists of $n$ elements each $\endgroup$ – user856 Aug 22 '13 at 5:48
  • $\begingroup$ @RahulNarain One could argue that the problem size there is actually $n^3$ rather than $n$. Shuffling and then re-orting the same set of $n$ numbers $n^2$ times might be better... $\endgroup$ – Steven Stadnicki Aug 22 '13 at 5:55
  • 3
    $\begingroup$ So vague! Given input of length $n$, just count it, ignore it, and do a single loop of size $n^3 \log n$ while printing something silly? $\endgroup$ – Evan Aug 22 '13 at 5:59
  • $\begingroup$ The computational model matters. Does @Evan's approach work on a Turing machine? $\endgroup$ – dfeuer Aug 22 '13 at 8:20
7
$\begingroup$

Given $a_,\ldots,a_n$, use a nested loop and quicksort to produce all values $a_i\operatorname{XOR}a_j\operatorname{XOR}a_k$ in sorted order. Or for something stupid

for i=1 to n
   for j=1 to n
      for k=1 to n
         m=n
         while (m>1)
            m = m/2

And finally, not that a simple

print("hello world")

is in $O(1)\subset O(n^3\log n)$

$\endgroup$
1
  • $\begingroup$ I would say that $O(1)$ is the best solution. For the case of $\Theta(n^3\log n)$ I think it is worth pointing out that the "stupid solution" might be wrong, that is, one has to assert that the input is really of size $n$, not $\log n$ (e.g. $n$ given in unary). $\endgroup$ – dtldarek Aug 22 '13 at 7:14
5
$\begingroup$

One very important point that hasn't been brought up yet is that the following 'algorithm' takes $O(n^3\log n)$ time:

for (i = 1; i < n; i++)
{
  count++;
}

In other words, if $f(n)=n$ then $f(n) = O(n^3\log n)$! This is because the notation $f(n) = O(g(n))$ (or my preferred form, $f(n)\in O(g(n))$) simply asserts that the 'worst case' of $f(n)$ is never worse than some multiple of $g(n)$; that is, that $f(n)$ is bounded from above by some multiple of $g(n)$. It makes no claims whatsoever about a lower bound on $f(n)$; for that, the notation should be $f(n)\in\Theta(g(n))$.

$\endgroup$
1
  • $\begingroup$ (Actually, now that I post this I see that Hagen mentioned this in an aside. All the same, I feel like the point is important enough to be expanded on.) $\endgroup$ – Steven Stadnicki Aug 22 '13 at 7:13
3
$\begingroup$

A one dimensional Fourier transform of a $n^3$ data, meaning $O(n^2 \times n \log n)$ operations with FFT.

$\endgroup$
3
  • $\begingroup$ simple operations?...i didnt get your statement $\endgroup$ – computer scientist Aug 22 '13 at 6:16
  • 1
    $\begingroup$ @computerscientist An FFT is computed using only addition and multiplication (and perhaps division depending on implementation), certainly counts as simple operations. $\endgroup$ – Thomas Aug 22 '13 at 12:53
  • 1
    $\begingroup$ Yeah, it uses simple operations, not so simple algorithm though. $\endgroup$ – Gummi F Aug 22 '13 at 18:51
2
$\begingroup$

If I understand big O notation correctly, then this is a ridiculously simple question. http://en.wikipedia.org/wiki/Big_O_notation

Problem: Sort a list

Algorithm: Choose any standard $O(n^2)$ algorithm you are familiar with.

Proof Let $f(n)$ be the worst case performance of the sorting algorithm for any list of size $n$. Clearly there must exist a constant $M$ such that for all sufficiently large values of $n$ $f(n)<Mn^2<Mn^3log(n)$.

$\endgroup$
0
$\begingroup$

Randomized local search solving OneMax of string length $n$ is $O(n \log n)$, hence if you have $O(n^2)$ strings/boxes, you get your complexity. More specifically:

You have a box full of white balls. You randomly select a box and examine it. If it is white, you replace it with a black one. If it is black, you keep it. A box (string) with $n$ balls solves/fills with all black balls in $n H_n = O( n \log n)$ trials ($H_n$ is harmonic number). Hence, if you have $O(n^2)$ such boxes...

$\endgroup$

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.