Question

Please calculate the Big-O cost and explain how:

1)

void recurX(long x) {
           if(x==0) System.out.print("*");  
else {
recurX(x/2);
recurX(x/2);
}

}

2)

void recurY(long y) {
           if(n==0) return;
           for(long i=0;i<y;i++)
System.out.print("*");
recurY(n/2);
       }

Answer 1

1)

void recurX(long x) {
if(x==0) System.out.print("*");
else {
recurX(x/2);
recurX(x/2);
}
}

Answer: O(n)
explanation:

Recurrence relation for running time :
T(n) = 2T(n/2)+1 // 2 recursive calls of size n/2, 1 for if condition
T(1) = 1//base case
solving:
T(n) = 2T(n/2)+1
= 2^2T(n/2^2)+2 +1
= 2^3T(n/2^3)+2^2 +2 +1
,
,
,
= 2^kT(n/2^k)+2^k-1 + ,,,,+2^2 + 2+1
let 2^k = n, k= logn
T(n) = 2^kT(n/n) +2^k-1 + ,,,,+2^2 + 2+1 = 2^k +2^k-1 + ,,,,+2^2 + 2+1 = 2^k+1 = 2*2^k = 2n = O(n)

2)

void recurY(long y) {
if(n==0) return;
for(long i=0;i<y;i++)
System.out.print("*");
recurY(n/2);
}
Answer: O(n)
Recurrence relation for running time :
T(n) = T(n/2) + n //recursive call of size n/2 , n for loop
T(1)=1//base case
solving:
T(n) = T(n/2) + n
=T(n/2^2) + n/2 + n
=T(n/2^3) +n/2^2 + n/2 + n
,
,
,
=T(n/2^k)+n/2^k-1+,,,, +n/2^2 + n/2 + n
let 2^k =n, k = logn
=T(n/n)+n/2^k-1+,,,, +n/2^2 + n/2 + n
=1 + n[ 1/2^k-1 + ,,,, + 1/2 + 1]
= O(n)