Java Time Complexity O(n^2/3)

Question

My math background is not so good, this is my attempt to write the JAVA code with runtime proportion to different input .

With n^2/3. Since n^2/3 = cube root n * cube root n, hence I can write

public void test(int n){
    for (int i = 0; i*i*i < n; i++) {
        for (int j = 0; j*j*j < n; j++) {
            count ++;
        }
    }
}

With 4^n. Can i use Fibonnaci method?

public int fibonnaci(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return fibonnaci(n - 2) + fibonnaci(n - 1);
    }
}

May I know if my code above is correct? thanks much!

2) Fibonacci - It is more of O(2^n) iso O(n^4). Use 4 nested for loops (which run from 1 to n incremented by 1) as an example of O(n^4) ;-) and 1) is a clever example :) — TJ-, Oct 14 '12 at 05:53

Bruno Reis · Answer 1 · 2012-10-14T06:30:27.257

The first one is correct, and really well thought.

The second one is not. That algorithm to calculate fibs has much higher time complexity than O(n^4) (EDIT: which was what was being asked when I wrote this answer -- the question has been updated meanwhile). It is not even polynomial. The reasoning is as follows (notation #fib(x): number of times fib is called to calculate fib(x)):

fib(1): #fib(1) = 1 (it returns directly the result)
fib(2): #fib(2) = 3 (one for fib(2), which calls it for fib(0) and fib(1))
fib(3): #fib(3) = 5 (one for fib(3), which calls it for fib(2) and fib(1), giving 3 + 1 more calls)
fib(4): #fib(4) = 9
fib(5): #fib(5) = 15
fib(6): #fib(6) = 25
...
fib(i): #fib(i) = 1 + #fib(i-1) + #fib(i-2)

So, you have:

#fib(i) ~= #fib(i-1) + #fib(i-2)

From this, it would be a reasonable guess that calculating fib(i) takes "about" (actually, just a little less than) 2 times the time to calculate fib(i-1). Hence, you could "guess" that O(#fib(i)) = O(2^i). This is the correct answer, which you can prove easily by induction.

Just to finish about the Fibonacci Sequence, there are much faster algorithms to calculate the n-th number. For instance, an algorithm with linear time (ie, O(n)) is to memoize that function you wrote (ie, make it consult a Map to check if it know the result for n, is so return it immediately, otherwise, calculate it, store it and return it). There's also a closed formula to calculate the n-th fib, therefore a constant-time algorithm (ie, O(1)).

Finally, an example of O(n^4) algorithm is anything with 4 inner loops, each loop running "about" n times.

For instance, calculate the volume of n cubes of side n (in a non-optimal way):

int volume = 0;
for (int cube = 0; cube < n; cube++)
  for (int x = 0; x < n; x++)
    for (int y = 0; y < n; y++)
      for (int z = 0; z < n; z++)
        volume++;
return volume;

@LouisWasserman, well noted. However, when I answered the question, it was asked about n^4, the OP changed it later, after I wrote this. Sorry for the inconvenience. — Bruno Reis, Oct 14 '12 at 06:24

score 1 · Answer 2 · edited May 23 '17 at 11:43

1

Are you just writing any code which takes time-complexity of that big-o bound?

Than for #1, yes, it would take O(n^(2/3)).

But for #2, your code would take O(2^n), and theta(1.6...^n), and 1.6.. is the famous golden-ratio number.

reference: Computational complexity of Fibonacci Sequence

edited May 23 '17 at 11:43

Community

1
1

answered Oct 14 '12 at 06:01

UGO

353
3
13

Stephen C · Answer 3 · 2012-10-14T06:38:17.690

This is not really an answer, but here is a sketch of a "cheat" solution to the problem of providing an example of a program that takes O(F(N)) time;

Create a Java function object to evaluate F(N) for a given N:
Pass it as a parameter to the following method:

   public void computeOrderFN(int n, FunctionInt2Int fn) {
      int count = fn.evaluate(n);
      for (int i = 1; i < count; i++) {
          // Do something O(1) that the compiler can't optimize away)
      }
   }

But don't use this if that there is a risk of losing credit for being "a smart**s" :-)

Java Time Complexity O(n^2/3)

3 Answers3