2.4k 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. $\text{M-W, N-V, O-U, P-X}$
2. $\text{M-W, N-U, O-X, P-V}$
3. $\text{M-V, N-W, O-X, P-U}$
4. $\text{M-W, N-U, O-V, P-X}$
edited | 2.4k views
0
It seems option of this question needs some correction.
+5
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)$
+4

Extended Master's Theorem ...

0
This is extended master theorem. Not original.
0
Ya i know ... Bt i found that its more effective than the real one ...
0
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)
answered by Veteran (367k points)
selected by
+1

log21 = 0.5

+1
corrected :)
+2
good work brother.... keep simple ... ;)
+1

log21 = 0  right? how 0.5

0

@arjun are you sure, it's corrected?

0

@Arjun sir what should we do for such question in GATE i.e answer not matches leave it or option d as it is around???

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

1)  by substitution = c)  O(n^2)

2)  by master's theorem case 2 = a)  O(n)

3)  by master's theorem case 2 =  b)  O(nlogn)

4.T(n) = T(n-1) + logn

T(n) = T(n - 1) + log n

= T(n - 2) + log (n - 1) + log n

= T(n - 3) + log (n - 2) + log (n - 1) + log n

= ...

= T(0) + log 1 + log 2 + ... + log (n - 1) + log n

= T(0) + log n!     = Θ(n log n)

answered by Boss (17.2k points)
0
How u got T(0)??????

Plz explain
+1 vote

1)  by substitution = c)  O(n^2)

2)  by master's theorem case 2 = a)  O(n)

3)  by master's theorem case 2 =  b)  O(nlogn)

4)  by substitution = b)  O(nlogn)

in 4th T(n)= T(0) + log 1 + log 2 + ... + log (n - 1) + log n

T(n)= T(0) + log(1*2*3*...........*n)

T(n)=log(n!)

T(n)=log(n^n)

T(n)=nlog(n)

answered by Active (4.6k points)

Please see the solution for the 3rd and 4th one using the substitution method --

3)    T(n)=T(n/2)+nlogn

=   nlogn + (n/2)log(n/2)+(n/4)log(n/4)+--------+T(n/2^k)

=  nlogn + (n/2)(logn-1)+(n/4)(logn-2)+(n/8)(logn-3)+-----------+T(n/2^k)

=  nlogn + (n/2)logn - n/2 + (n/4)logn - n/2 + (n/8)logn - 3n/8 + -------------

=  nlogn(1 + 1/2 + 1/4 + 1/8 + -------------------) - n(1/2 + 1/2 + 3/8 + 1/4 + 5/32 + --------)

For the infinite series (1 + 1/2 + 1/4 + 1/8 + -------------------) solution will be 2.

=  nlogn*2  - n*(very small value near around 2)

= O(nlogn)

4) T(n) = T(n-1) + logn

=  logn + log(n-1) + log(n-2) + log(n-3) + log(n-4) + ------------

= logn + logn + logn + logn + ------------------------------ + logn (we are taking logn as upper bound for Big Oh notation)

= O(logn * logn)

= O(log^2n)

answered by (293 points)
0
am talking about 4th one: logn + logn +.....+  ..... it will go till nth term so it should be logn * n ryt?
+1

I think 4th one should be O(nlogn) because it simplifies to log[n(n-1)(n-2)...........(n-(n-2))] which equals to log(nn)which is equal to nlogn

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

answered by Boss (11.7k points)
edited
+1
If you understood the formula, apply it and show it for the last case.
0
Using the formula i hav mentioned ?? its nt in that form to apply ... simple substitution thats enough for P i guess ...
0
I do not see any (n-1) in the image you posted, then how you applied the formula?
0
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 ...
0

Puja Mishra

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

1
2