Provide an algorithm $O (n ^ 3 \log n)$, any example?

Question

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!

Answer 1

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

Answer 2

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...

Answer 3

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)$

Answer 4

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))$.

Answer 5

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)$.