The recurrence T (n) = 7T (n / 2) + n 2 describes the running time of

1.	The recurrence T (n) = 7T (n / 2) + n 2 describes the running time of an algorithm A. Another algorithm B has a running time of T’(n) = k T’(n/ 4) + n 2
Answer» Answer: From the question the given recurrence relation is T(N)=7T(n/2)+n^2 while its solution is by the MASTER theorem of asymptotic complexity T(n)=Θ(n^log49base4). So, the general formulate of the complexity can be given as the recurrence relation T′(n)=αT′(n/4)+n^2. So, from the relation we have that, a=α,b=4,f(n)=n^2 n^loga base b=n^logα base 4, for the value of the α>16, f(n)=O(n^logα−ξ) where the ξ>0. Therefore, for α>16: T′(n)=Θ(n^logα base 4) Now A has to HOLD, for becoming asymptotically faster than A':- n^logα base 4 Consequently the value of α so that A′ is asymptotically faster than A will bet the value of 48. Explanation:

The recurrence T (n) = 7T (n / 2) + n 2 describes the running time of an algorithm A. Another algorithm B has a running time of T’(n) = k T’(n/ 4) + n 2

Answer»

Answer:

From the question the given recurrence relation is T(N)=7T(n/2)+n^2 while its solution is by the MASTER theorem of asymptotic complexity T(n)=Θ(n^log49base4). So, the general formulate of the complexity can be given as the recurrence relation T′(n)=αT′(n/4)+n^2.

So, from the relation we have that, a=α,b=4,f(n)=n^2

n^loga base b=n^logα base 4, for the value of the α>16, f(n)=O(n^logα−ξ) where the ξ>0.

Therefore, for α>16: T′(n)=Θ(n^logα base 4)

Now A has to HOLD, for becoming asymptotically faster than A':-

n^logα base 4

Consequently the value of α so that A′ is asymptotically faster than A will bet the value of 48.

Explanation:

Discussion

No Comment Found

Related InterviewSolutions

Which sign is semicolom
There are 10,48,576 rows by 16,384 columns in excel true ot false
Comppund formula having single mathematical operator
Which is the best interpretation of the graph?A. A small amount of anxiety is not enough to help the students perform better on a test.B.The higher a student's anxiety, the greater the probability of a good test score.C. A small amount of anxiety can help students perform better on tests.D. The higher a student's anxiety, the lower the likelihood of overcoming it.
मेरी आमा र म निबन्ध
1. Which key is not used for selecting a range of cell in a worksheet?b. Shiftd. None of thesea. Ctrlc. Alt
List of Bidentate and monodentate ligands
What is Cycle case? Explain with example.
(9),CEF in base 16 to base 10
State whether it is true or false.1. 5X6 means a table with columns of 5 rows T or F2. MS PowerPoint is spreadsheet software T or F