edited by
14,833 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

2 votes
2 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)  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)

0 votes
0 votes

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

edited by
0 votes
0 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)  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)

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,385 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 ...