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$

| 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

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
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.

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

0

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

+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.

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