The Gateway to Computer Science Excellence
0 votes
151 views

Which of the following functions given by their recurrences grows the fastest asymptotically?

  1. $T(n) = 8T(n/4) + 100n^2$
  2. $T(n) = 81T(n/9) + 10n^2$
  3. $T(n) = 16T(n/4)+ 100(n \log n)^{1.99}$
  4. $T(n) = 100T(n/100)+ n \log^2 n$

 

in Algorithms by Active (1.8k points) | 151 views
0
Just find the big-O notation for all the recurrences and the one with the largest value grows the fastest.

For example, $O(n^2)$ grows faster than $O(n)$ for large values of $n$. (We consider large values of $n$ since that is what asymptotic notation is used for.)
0
then f1 =0(n^2 )

 f2= 0(n^2logn)

f4=0(nlog^3n)

can you solve value of f3 by using master theoram then i judge my answer.
0
i also try using same method which you say but i fail to calculate the value of f3 using master theoram.
+2

Shubham Aggarwal,

Please add $\underline{\text{name of test series}}$

0
F3 IS 0(N^2) using master thoerems
0
I think it will be more than that because by ignoring 100, its n^2 log^3 n
0
no need of doing that.just use master theorem(advanced one)
0
testbook
0
adarsh_1997 can you upload the solution of n3 . thanks in advance
0

anwer is 2 as

f1 is O(n2)

f2 is O(n2logn)

f3 is O(n2)

f4 is O(nlog3n)

whenever we are comparing complexities we assume n to be larger numbers.

so the answer is B

0
then n^2 is not a larger number.???
0

if n is large than n2 will be larger ofcourse, But of all the complexitites n2logn will be largest of all. 

0

testbook

Shubham Aggarwal,

add it to the title 

0

Hemanth_13 , 

do you know you cannot post some non-standard materials picture here?

0

Sorry Subarna Das, my intension was not that just wanted to show what used to solve if there is any mistake in that I would get corrected. Thanks

0

adarsh_1997 How did you get O(n^2), please explain.

 

+1

t(n)=16t(n/4)+100 n1.99log1.99n

a=16 b=4   bk=41.99=15.77

a>bk

t(n)=0(nlogba)=0(n2)

0
Cool got it. Unfortunately i rounded 1.99 to for quick calculation and it moved into other category :P
0
ok bro btw the advanced master theorem i was talking about was the one you posted the photo of.

btw virtual calculator will be there in exam.no way of running from this values
0
that's the explanation which i want.

1 Answer

+3 votes
Best answer

A function $f$ is asymptotically larger than function $g$ means for large values (all numbers greater than some finite number) $f(n) > g(n).$

$T(n) = 81T\left( \dfrac{n}{9} \right) + 10n^2$ -- This recurrence will asymptotically grow faster than all the other options given.


By applying Master's Theorem'

  1.  $T(n) = 8T \left( \dfrac{n}{4} \right) + 100n^2$
    Recursion part, $n^{\log_b a} = n^{\log_4 8}$ and $f(n) = 100 n^2.$ Since, $f(n)$ is polynomially (by a factor of some $n^{\epsilon}, \epsilon > 0)$larger, and $f(n)$ is regular, as per Master Theorem Case 3,  $$T(n) = \Theta(f(n))= \Theta(n^2)$$
  2.  $T(n) = 81T \left( \dfrac{n}{9} \right) + 10n^2 \\ \therefore T(n) = O(n^2\log n)$
    Recursion part, $n^{\log_b a} = n^{\log_9 81} = n^2$ and $f(n) = 10 n^2.$ Since, $f(n) = \Theta (n^{\log_b a}),$ as per Master Theorem Case 2,  $$T(n) = \Theta(f(n) \log n)= \Theta(n^2 \log n)$$
  3.  $T(n) = 16T \left( \dfrac{n}{4} \right) + 100(n\log n)^{1.99}$
    Recursion part, $n^{\log_b a} = n^{\log_4 16} = n^2$ and $f(n) = 100 (n \log n)^{1.99}.$ Since, $f(n)$ is polynomially (by a factor of some $n^{\epsilon}, \epsilon > 0)$ smaller, as per Master Theorem Case 1,  $$T(n) = \Theta(n^{\log_b a})= \Theta(n^2)$$
  4.  $T(n) = 100T \left( \dfrac{n}{100} \right) + n\log^2n$
    Recursion part, $n^{\log_b a} = n^{\log_{100} 100} = n$ and $f(n) = n \log^2 n .$ Here $f(n)$ and $n^{\log_b a}$ are not asymptotically equal and they dont have a polynomial difference. (Any polynomial in $n$ is asymptotically larger than any polynomial in $\log n).$ So Master Theorem cannot be applied as such. But we can apply the Extended Master Theorem Case 2, which states that $$\text{if}\; f(n) = \Theta(n^{\log_b a} \log^k n), k > -1, \text{ then }T(n) = \Theta(n^{\log_b a} \log ^{k+1} n)$$
    Here, $k = 2.$ So, we get $$T(n) = \Theta(n \log^3 n)$$

Reference: Master Theorem

by Boss (15.4k points)
selected by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
198,209 comments
104,890 users