Big O Proof, how to?

Question

I don't understand how to find the complexity of this function. How do I set up the math. Could you please help me out with general tips as well, since I'm very confused with big O notation Thanks

The answer should be O(n^(1/3))

void fun (int n){
 int i=0; 
   while(i*i*i<=n){
     i++;
   }
}

hint: at what fraction of N will the loop terminate? – Mitch Wheat Apr 16 '18 at 03:50 — Mitch Wheat, Apr 16 '18 at 03:50

score 0 · Answer 1 · answered Apr 16 '18 at 04:11

There's a very good answer here: https://stackoverflow.com/a/13467808/6854069

I'm assuming you are trying to calculate time complexity. In that case, if your while loop is

while(i<=n){
    i++;
}

then it will take "n" iterations for "i" to reach the value "n". Hence the time complexity is O(n).

Since you are trying to reach "n" at the rate of i^3, the time you will take to reach the value of "n" is i^(1/3). O(n) representation of this is O(n^(1/3)). Your while loop can also be represented as:

while(i<=n){
    i++;
    i = i*i*i;
}

O(n) representation for time complexity = the number of iterations you take to reach the desired value.

Big O Proof, how to?

1 Answers1