search
Log In
0 votes
253 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 253 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


selected by
Answer:

Related questions

7 votes
1 answer
1
419 views
Consider the following piece of pseudo-code: A(n){ if(n==0) return 1; return A(√n) + B(n) + C(n) + D(n); } B(n){ if (n==0) return n; return B(n-1); } C(n){ return A (√n); } D(n){ return n; } What is the time complexity in terms of Big $\Theta$ notation for the function call to procedure A? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n \log \log n)$ $\Theta(n^2 \log n)$
asked Dec 27, 2018 in Algorithms Ruturaj Mohanty 419 views
0 votes
0 answers
2
137 views
How to solve the following recurrence relation? T(n) = T(n-6) + n2 , n>7 T(n) = 1 , n<= 7
asked Nov 17, 2018 in Algorithms garvit_vijai 137 views
1 vote
1 answer
3
209 views
how to compute time complexity of this kind of recurrence relation- T(n)=T(n/2)+T(n/4)+T(n/8)+n
asked Oct 27, 2018 in Algorithms aditi19 209 views
0 votes
4 answers
4
2.4k views
I was wondering whether the recurrence T(n) = T(n/2) + 2n could be solved by using master theorem, and what would be the way. I tried solving the recurrence but can't. There is no mention to it in CLRS book. Please help. Thanks in advance.
asked Sep 28, 2018 in Algorithms mohitrai0_0 2.4k views
...