HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
logwithruntimefunctionwriteattemptcubedcomplexity

Problem

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.

Solution

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;
}

Code Snippets

public void run (int n) {
    return;
}
// 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;
}

Context

StackExchange Computer Science Q#2411, answer score: 4

Revisions (0)

No revisions yet.