CODE:
void fun(int n){ if(n>2){ for(int i=0;i<n;i++){ j=0; while(j<n){ cout<<j; j++; } } fun(n/2); } } Here's what I think: The recursive part is running log(n) times ? and during each recursive call, the for loop will run n^2 times, with n changing to half in each recursive call. So is it n^2 + (n^2)/4 + (n^2)/16 + ... + 1?
The number of writes to cout is given by the following recurrence:
T(N) = N² + T(N/2). By educated guess, T(N) can be a quadratic polynomial. Hence
T(N) = aN²+bN+c = N² + T(N/2) = N² + aN²/4+bN/2+c. By identification, we have
3a/4 = 1 b/2 = 0 c = c. and
T(N) = 4N²/3 + c. With T(2)= 0,
T(N) = 4(N²-4)/3 which is obviously O(N²).
This is simple mathematics. The complexity is n^2 + (n^2)/4 + (n^2)/16 + ... + 1. It is (n² * (1 + 1/4+ ...)) . And the maths says that the infinite serie converges to 4/3 (the formula is: 1 / (1 - 1/4)).
It gives actually O(n2).
