Please answer these doubts related to Quiz on Divide and Conquer

#1
  1. Let T(n)= T(n-1) + 1/n. Then T(n) is:

Ѳ (1)

Ѳ (log n)

Ѳ (log log n)

Ѳ (n)

  1. Which of the following algorithms is NOT a divide & conquer algorithm by nature?

Heap Sort

Euclidean algorithm to compute the greatest common divisor

Cooley-Tukey fast Fourier transform

Quick Sort

  1. Consider the following function

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;
}
}
Assume that the division operation takes constant time and “sum” is global variable. What is the time complexity of “find (n)” ?

n^2

n^3

n^2logn

None of these

  1. Maximum Subarray Sum problem is to find the subarray with maximum sum. For example, given an array {12, -13, -5, 25, -20, 30, 10}, the maximum subarray sum is 45.
    The naive solution for this problem is to calculate sum of all subarrays starting with every element and return the maximum of all. We can solve this using Divide and Conquer, what will be the worst case time complexity using Divide and Conquer.

O(logN)

O(N)

O(NlogN)

O(N^2)

  1. The number of comparisons required to find maximum and minimum in the given array of n- element using divide and conquer:

ciel(3n/2)

ciel(3n/2)+2

floor(3n/2)

floor(3n/2)-2

  1. What is the complexity of the following recurrence :
    7T(n/2) + an^2

O(n^2)

O(n^1.51)

O(nlogn)

O(n^2.81)

O(long)

  1. What will be the time complexity of the following recurrence relation:
    3T(n/3)+ √n

O(√n)

O(n)

O(nlogn)

O(n^2)

#2

It can be easily seen (or proven formally with induction) that T(n) is the sum of 1/k for the values of k from 1 to n. This is the n th harmonic number, Hn = 1 + 1/2 + 1/3 + … + 1/n.

Asymptotically, the harmonic numbers grow on the order of log(n). This is because the sum is close in value to the integral of 1/x from 1 to n, which is equal to the natural logarithm of n. In fact, Hn = ln(n) + γ + O(1/n) where γ is a constant. From this, it is easy to show that T(n) = Θ(log(n)).

Heap sort isnt

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)

image
image600×503 33.2 KB
image
image913×369 48.2 KB

Refer here : Divide and Conquer Quiz Question

see this carefully
T(n) = 7T(n/2) + 3n^2 + 2
As one can see from the formula above:
a = 7, b = 2, and f(n) = 3n^2 + 2
So, f(n) = O(n^c), where c = 2.
It falls in master’s theorem case 1:
logb(a) = log2(7) = 2.81 > 2
It follows from the first case of the master theorem that T(n) = ?(n^2.8) and implies O(n^2.8) as well as O(n^3).
image

use master theorm for this recurrence.

#3

hello @sahilkhan2312000131i think you have reopened the doubt i think you have done it by mistake .
if you have any thing in doubt you can confirm here .
Happy Learning !!

#4

Can you please tell what is n2 in the following code:
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;
}
}

#5

hey @sahilkhan2312000131 are you sure there is n2 in the question ?

#6

yes…you can check the reply of @Kartikkhariwal1 above where he has answered it.

#7

Hey @sahilkhan2312000131

I JUST QUOTED UR QUESTIONS

its actually find(n/2)

#8

yes @sahilkhan2312000131i was thinking the same it must be n/2 that’s why i have confirmed from you if you are sure about n2.
i hope your doubt is cleared now .
if you still have any doubt you can ask here .
Happy Learning !!

#9

Can you please explain me more clearly how the following function has order of O(n^2logn)
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;
}
}

#10

@sahilkhan2312000131 see in each step of second loop for n it will run till n^2 and in th first lopp we are diving n by n/2 so it will take n^2steps for log n times .
that is why the time complexity is (n^2log(n)).
if you still have any doubt you can ask here .
Happy Learning !!

#11

is it n^(2logn) or (n^2)*logn

#12

hey @Kartikkhariwal1 Can you please tell me why you have written 3n^2 + 2 in the following lines to find the complexity of 7T(n/2) + an^2.

T(n) = 7T(n/2) + 3n^2 + 2
As one can see from the formula above:
a = 7, b = 2, and f(n) = 3n^2 + 2
So, f(n) = O(n^c), where c = 2.
It falls in master’s theorem case 1:
logb(a) = log2(7) = 2.81 > 2
Can we simply say that c=2 for 7T(n/2) + an^2 because of an^2, and since log2(7) = 2.81 > 2, this implies case 1 of master’s theoram. So, complexity is O(n^2.81)

#13

Hey @sahilkhan2312000131
a is any constant so i subsituted it but since we are not using it anywhere u can consider it a

#14

@Kartikkhariwal1 are you taking this doubt ?

#15

No @tusharaggarwal272 ,feel free to answer
He quoted me so I have to reply back :slight_smile:

#16

@tusharaggarwal272 is it n^(2logn) or (n^2)*logn

#17

@sahilkhan2312000131 it is (n^2)*logn

#18

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.