mercredi 11 février 2015

What is the run time of the following statement in big oh notation?


public int foo ( int x , int k ) {
if ( x <= k )
return 1;
else
return foo ( x / k , k ) + 1;
}


From my understanding, the runtime of this should equal the runtime of the conditional + the runtime of the larger if/else statement.


However, I'm having trouble determining the correct runtime of the statement "return foo(x/k, k) + 1". Would this be constant? The increase of x and k doesn't seem to have an effect on the runtime, as it is the ratio between them that is important for the outcome.


Any clarity would be much appreciated. Thanks!


Aucun commentaire:

Enregistrer un commentaire