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

The Gateway to Computer Science Excellence

0 votes

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

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

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

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.

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.

0

anwer is 2 as

f1 is O(n^{2})

f2 is O(n^{2}logn)

f3 is O(n^{2})

f4 is O(nlog^{3}n)

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

so the answer is B

0

if n is large than n^{2} will be larger ofcourse, But of all the complexitites n^{2}logn will be largest of all.

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

+1

t(n)=16t(n/4)+100 n^{1.99}log^{1.99}n

a=16 b=4 b^{k}=4^{1.99}=15.77

a>b^{k}

t(n)=0(n^{log}^{ba})=0(n^{2})

0

Cool got it. Unfortunately i rounded 1.99 to for quick calculation and it moved into other category :P

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

- $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)$$ - $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)$$ - $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)$$ - $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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,291 answers

198,209 comments

104,890 users