How is this N^2 log n?

#1

find (int n)
{
if (n < 2 ) then return;
else
{
sum= 0;
for (i= 1; i ≤ 4; i++) find (n2);
for (i=1; i≤ n*n; i++) sum= sum + 1;
}
}

#2

hello @nilotpal

here they are calling find(n/2) right?

#3

Yes. that should be n/2

#4

ok,

from one state n we are calling state n/2 four times right?
and in each state we are doing work (value of n) ^2 (the second loop) right?

in state n we have done n ^ 2 and call state n/2

at state n/2 we have done (n/2)^2 work which is n^2 / 4 . and becuase 4 such states are there in this level. total work done is 4 * (n^2/4) = n^2
which is same as state n right?
it means if we draw the recusion tree then summation of work done at every level will n^2.

now total how many levels will be there? since every time we are divinding by 2.(i.e n,n/2 , n/2^2 , n/2^3…)
we will gave logn n level.

so time complexity we can wrtie as -> work done at everry level of tree * number of levels
=> n^2 * log(n)

#5

yes, so the recursive funvtion should be T(n) = 4 T(n/2) + n^2 ?? right??

#6

correct . . … . …
/…
…

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.