The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 votes

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
asked in Algorithms by Veteran (59.4k points)
edited by | 1.7k 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) ???

3 Answers

+27 votes
Best answer
(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)$


$=\Theta(n \log n)$  (Stirling's Approximation)
answered by Veteran (342k points)
selected by

log21 = 0.5  surprise

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

log21 = 0  right? how 0.5

+9 votes
M-W, N-U and Both O and P will have V..I guess wrong choices!
answered by Loyal (6.9k points)
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
0 votes


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

answered by Boss (10.4k points)
edited by
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& for option D we can't apply this.

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

35,506 questions
42,827 answers
42,181 users