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$
5
  • 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, 2012 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, 2012 at 16:31
  • $\begingroup$ @phg Is my logic wrong? And if yes, could you please point out where is wrong $\endgroup$
    – Timeless
    Jun 15, 2012 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, 2012 at 16:50
  • 2
    $\begingroup$ You can also be pedantic and give binary search: $O(\dots)$ allows asymptotically faster algorithms. $\endgroup$
    – Raphael
    Jun 19, 2012 at 19:13

2 Answers 2

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$
1
  • $\begingroup$ It is allowed, but our lecturer recommend us to write the function without using math library. $\endgroup$
    – Timeless
    Jun 15, 2012 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
  • 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, 2012 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.