Optimise this function ! - Interview

Time : 30 minutes

Question

Optimise this function :

f(int n){

if (n == 0) return 1;

if (n == 1) return 2;

return f(n-1)+f(n-1);

}

Analyse :

Normally, people will easily optimise this O(n*n) algorithm to O(n) by doing return fun(n-1)*2. Usually, people then will understand that this function does 2 power n so people uses pow from the cmath library. Then people might find that we can do 2 power n, simply by bit operation : (1<<n).

Source : Geeks for geeks