1.5k views

If $T_1 = O(1)$, give the correct matching for the following pairs:

 (M) $T_n = T_{n-1} + n$ (U) $T_n = O(n)$ (N) $T_n = T_{n/2} + n$ (V) $T_n = O(n \log n)$ (O) $T_n = T_{n/2} + n \log n$ (W) $T = O(n^2)$ (P) $T_n = T_{n-1} + \log n$ (X) $T_n = O(\log^2 n)$
1. M-W N-V O-U P-X
2. M-W N-U O-X P-V
3. M-V N-W O-X P-U
4. M-W N-U O-V P-X
edited | 1.5k views
It seems option of this question needs some correction.
1. $T(n) = T(n-1) + n$ is $Θ(n^2)$ [Note:- This recurrence relation is for the worst case of Quick Sort]
2. $T(n) = T(n/2) + n$ is $Θ(n)$
3. $T(n) = T(n/2) + nlogn$ is $Θ(nlogn)$
4. $T(n) = T(n-1) + logn$ is $Θ(nlogn)$

## Extended Master's Theorem ...

This is extended master theorem. Not original.
Ya i know ... Bt i found that its more effective than the real one ...
can you please tell me how to solve T(n) = 2T( sqt(n) + log(2^k)  ( sorry i dont know how to use square root symbol) ???

(M) $T(n)$ = Sum of first n natural numbers = $\frac{n(n+1)}{2} = O(n^2)$

(N) $T(n) = \Theta(n) =O(n)$, third case of Master theorem

($f(n) = n = \Omega \left(n^{\log_b a+ \epsilon}\right) = \Omega \left(n^{\log_2 1 + \epsilon}\right) = \Omega\left(n^{0 + \epsilon}\right)$, satisfied for any positive $\epsilon \leq 1$. Also, $af\left(\frac{n}{b}\right) < cf(n) \implies f\left(\frac{n}{2}\right) < cf(n) \implies \frac{n}{2} < cn$, satisfied for any $c$ between $0$ and $0.5$)

(O) $T(n) = \Theta(n \log n) = O (n \log n)$, third case of Master theorem

($f(n) = n \log n =\Omega\left(n^{\log_b a+ \epsilon}\right) = \Omega \left(n^{\log_2 1 + \epsilon}\right) = \Omega\left(n^{0.5 + \epsilon}\right)$, satisfied for positive $\epsilon = 0.5$. Also, $af\left(\frac{n}{b}\right) < cf(n) \implies f\left(\frac{n}{2}\right) < cf(n) \implies \frac{n}{2} \log \frac{n}{2} < cn \log n$, satisfied for $c = 0.5$)

(P) Like in (M), here we are adding the log of the first n natural numbers. So,

$T_n = \log 1 + \log 2 + \log 3 + \dots + \log n$

$=\log (1\times 2\times \dots \times n)$

$=\log(n!)$

$=\Theta(n \log n)$  (Stirling's Approximation)
selected by

log21 = 0.5

corrected :)
good work brother.... keep simple ... ;)

log21 = 0  right? how 0.5

M-W, N-U and Both O and P will have V..I guess wrong choices!
Yes. O and P must be $O(n \log n)$.
@Arjun sir Answer is D selected but no option is actually matched
yes, no option matches

Solve using this formula .... not sure  D will be the answer because P will be nlogn ..

edited
If you understood the formula, apply it and show it for the last case.
Using the formula i hav mentioned ?? its nt in that form to apply ... simple substitution thats enough for P i guess ...
I do not see any (n-1) in the image you posted, then how you applied the formula?
No its nt there ... Do i need to mention that thing also ... if it is nt in that form use another approach ?? then i will take care of it next time ...

Puja Mishra

This formula is for master therom of D&C.so for option D we can't apply this.