Dividde and conquer quiz

#1

Could you explain question 1,7,8. How is their time complexity calculated.

#2

Consider the following function

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

Assume that the division operation takes constant time and “sum” is global variable. What is the time complexity of “find (n)” ?

for this ans is n^2logn

in each function call n^2 steps
and total function call is of the order log n because we are dividing by 2 each time
so time complexity O(n^2 logn)

1 Like
#3

which one are 7th and 8th??

#4

image image

image
image504×541 5.68 KB

these are the questions 7 and 8. have also included 1.

Solutions required
#5

And thanks for the explanation i understand it now!