The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+20 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)$ |

- $\text{M-W, N-V, O-U, P-X}$
- $\text{M-W, N-U, O-X, P-V}$
- $\text{M-V, N-W, O-X, P-U}$
- $\text{M-W, N-U, O-V, P-X}$

+29 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)$

$=\log(n!)$

$=\Theta(n \log n)$ (Stirling's Approximation)

(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)

+10 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.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)

+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)

0 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)

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.6k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.3k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 480
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,748 questions

47,471 answers

145,586 comments

62,234 users