Provide an algorithm $O (n ^ 3 \log n)$, any example? 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!
 A: 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)$
A: 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))$.
A: A one dimensional Fourier transform of a $n^3$ data, meaning $O(n^2 \times n \log n)$ operations with FFT.
A: 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)$.
A: 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...
