# 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!

• @Amzoti yes...only that – computer scientist Aug 22 '13 at 5:38
• Sort $n^2$ lists of $n$ elements each – user856 Aug 22 '13 at 5:48
• @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... – Steven Stadnicki Aug 22 '13 at 5:55
• 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? – Evan Aug 22 '13 at 5:59
• The computational model matters. Does @Evan's approach work on a Turing machine? – dfeuer Aug 22 '13 at 8:20

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

• 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). – dtldarek Aug 22 '13 at 7:14

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

• (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.) – Steven Stadnicki Aug 22 '13 at 7:13

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

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

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

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