edited by
14,834 views
45 votes
45 votes

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 by

8 Answers

Best answer
56 votes
56 votes
(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$ greater than $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)
edited by
15 votes
15 votes
M-W, N-U and Both O and P will have V..I guess wrong choices!
8 votes
8 votes

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)

2 votes
2 votes

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) 

Answer:

Related questions

36 votes
36 votes
2 answers
1
29 votes
29 votes
3 answers
2
Kathleen asked Sep 23, 2014
11,446 views
The maximum gate delay for any output to appear in an array multiplier for multiplying two $n$ bit numbers is$O(n^2)$$O(n)$$O(\log n)$$O(1)$
35 votes
35 votes
4 answers
4
Keith Kr asked Sep 12, 2014
14,387 views
The minimum number of record movements required to merge five files A (with $10$ records), B (with $20$ records), C (with $15$ records), D (with $5$ records) and E (with ...