Attempt to write a function with cubed log runtime complexity $O(\log^3 n)$

I'm learning Data Structures and Algorithms now, I have a practical question that asked to write a function with O(log3n), which means log(n)*log(n)*log(n).

public void run(int n) {
for (int i = 1; i < n; i *= 2) {
for (int j = 1; j < n; j *= 2) {
for (int k = 1; k < n; k *= 2) {
System.out.println("hi");
}
}
}
}

I have come with this solution, but it seems not correct. Please help me out.

migrated from stackoverflow.comJun 19 '12 at 15:19

This question came from our site for professional and enthusiast programmers.

• Is that all you have to do? Have you tried to compute log3n first and then have the program wait for the specified amount of time :) – Boris Stitnicky Jun 15 '12 at 16:30
• Yeah. The simplest way for that would be to replace every n with floor(log(n)). – phg Jun 15 '12 at 16:31
• @phg Is my logic wrong? And if yes, could you please point out where is wrong – Timeless Jun 15 '12 at 16:34
• It is correct. 3 nested fors make a ^3, and multiplying with 2 approaches n logarithmically. There's just a trivial way to "construct" a desired complexity O(f(n)) by doing for(int i=0; i<f(n); i++), as pointed out by usr. – phg Jun 15 '12 at 16:50
• You can also be pedantic and give binary search: $O(\dots)$ allows asymptotically faster algorithms. – Raphael Jun 19 '12 at 19:13

Your program is correct. Your could also iterate Math.Log(n)*Math.Log(n)*Math.Log(n) times. Not sure if that is considered cheating.

• It is allowed, but our lecturer recommend us to write the function without using math library. – Timeless Jun 15 '12 at 16:36

The following trivially is in the complexity class $O(\log^3 n)$:

public void run (int n) {
return;
}

But here is a solution with average and worst case of $O(\log^3 n)$:

// O(log(n)), n = |orderedVals|
int findClosest (int needle, int[] orderedVals) {
// binary search for closest value and return it
}

// O(log(n)^3), n = |orderedVals|
int weirdSum (int initialNeedle, int[] orderedVals) {
int sum = 0;
int needle1 = initialNeedle;
int needle2 = findClosest(needle1, vals);
for (int i = 0; i < needle2; ++i) {
int needle3 = findClosest(needle2, vals);
for (int j = 0; i < needle3; ++j) {
sum += findClosest(needle2, vals);
}
}
return sum;
}
• The first algorithm also has an average and worst-case run-time of $O(\log^3 n)$. Perhaps you meant $\Theta(\log^3 n)$? – JeffE Jun 22 '12 at 3:08