4
$\begingroup$

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.

$\endgroup$

migrated from stackoverflow.com Jun 19 '12 at 15:19

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

  • 1
    $\begingroup$ 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 :) $\endgroup$ – Boris Stitnicky Jun 15 '12 at 16:30
  • 2
    $\begingroup$ Yeah. The simplest way for that would be to replace every n with floor(log(n)). $\endgroup$ – phg Jun 15 '12 at 16:31
  • $\begingroup$ @phg Is my logic wrong? And if yes, could you please point out where is wrong $\endgroup$ – Timeless Jun 15 '12 at 16:34
  • 1
    $\begingroup$ 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. $\endgroup$ – phg Jun 15 '12 at 16:50
  • 2
    $\begingroup$ You can also be pedantic and give binary search: $O(\dots)$ allows asymptotically faster algorithms. $\endgroup$ – Raphael Jun 19 '12 at 19:13
6
$\begingroup$

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.

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

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;
}
$\endgroup$
  • 1
    $\begingroup$ The first algorithm also has an average and worst-case run-time of $O(\log^3 n)$. Perhaps you meant $\Theta(\log^3 n)$? $\endgroup$ – JeffE Jun 22 '12 at 3:08

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.