3k views

If $T_1 = O(1)$, give the correct matching for the following pairs:
$$\begin{array}{l|l}\hline \text{(M) T_n = T_{n-1} + n} & \text{(U) T_n = O(n)} \\\hline \text{(N) T_n = T_{n/2} + n} & \text{(V) T_n = O(n \log n)} \\\hline \text{(O) T_n = T_{n/2} + n \log n} & \text{(W) T_n = O(n^2)} \\\hline \text{(P) T_n = T_{n-1} + \log n} & \text{(X) T_n = O(\log^2 n)} \\\hline \end{array}$$

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 | 3k views
0
It seems option of this question needs some correction.
+7
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)$
+5

Extended Master's Theorem ... 0
This is extended master theorem. Not original.
+1
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)
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

For those who can't understand $log(n!) = O(nlogn)$

https://stackoverflow.com/questions/2095395/is-logn-%CE%98n-logn

M-W, N-U and Both O and P will have V..I guess wrong choices!
+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)

0
How u got T(0)??????

Plz explain

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)

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

0

@piyushkr

How it becomes log n * log n = log^2 n

+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) Solve using this formula .... not sure  D will be the answer because P will be nlogn ..

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