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 .

1. 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 ++;
           }
       }
   }
   

2. 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!

Answer 1

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;

Answer 2

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