recategorized by
640 views
4 votes
4 votes
Consider the following code…..

Search(int n){
if(n<2)
then return;
else{
s=0;
for(i=1;i<=8;i++){
Search(n/2);
}
for(i=1;i<n*n;i++){
for(j=1;j<n;j=j*2){
s=s+i;
}
}
}
}

Assume s is a global variable.Find the complexity of the given Search(n)?
recategorized by

1 Answer

Best answer
5 votes
5 votes

For recursive code , we find time complexity by writing the recurrence relation first and then using Master Theorem or Recursion tree approach to find the complexity..

For the recurrence equation :

T(n)  =   a T(n / b)   +   f(n)

a denotes the number of recursive subproblems , 'n/b' being the size of each problem and f(n) being the time taken in the non recursive part of the entire code..

Here in the given code we are calling function 8 times indirectly by using the while loop..

Hence a  =  8 here ..Also b = 2 as we have used "search(n/2)" as recursive call..

Now for f(n) , we have to calculate complexity of non recursive part which is the nested for loop in the given code that follows recursive calls..

Hence coming to for loop :

i runs n2 times and for each value of 'i'  ,   'j' runs log2n due to the increment step j = j * 2..

Hence total times 'j' runs including all values of 'i'   =   O(n2 logn)

Thus f(n) can be taken as O(n2logn)

Thus the recurrence relation for the entire code is written as :

T(n)    =    8T(n/2)   +   O(n2 logn)

Now  here  nlogba   =   n3 here which is polynomial times greater than n2 logn..

Thus T(n)  =  O(n3) for the given code which is the required complexity..

selected by

Related questions

5 votes
5 votes
2 answers
1
shaurya vardhan asked Nov 2, 2017
1,642 views
Consider the following functionVoid func(int n){Int k=n;Int i=0;for(;i<n;i++){while(k>1){k>>=1;}}What is the worst case time complexity of the function?
1 votes
1 votes
0 answers
2
kartikeya2812 asked Jun 16, 2018
387 views
What will be the time complexity of the following algorithm ?A(n){if(n<=1) return 1;for(i=1;i<n;i++){ for(j=0;j<3;j++){ A(n-1) } }}
5 votes
5 votes
0 answers
3
Mk Utkarsh asked Jan 9, 2018
407 views
T(n) $\leq$ T($\frac{n}{5}$) + T($\frac{7n}{10}$) + 15nT(n) $\leq$ 5 when n $<$ 6