Top Algorithms Interview Questions

Mobiprep handbooks are free downloadable placement preparation resources that can help you ace any company placement process. We have curated a list of the 40 most important MCQ questions which are asked in most companies such as Infosys, TCS, Wipro, Accenture, etc. The placement handbooks also have detailed explanations for every question ensuring you revise all the questions with detailed answers and explanations.

Question

Explanation

Consider the Recurrence relation
T (n) = 2T(n/2)+n n>1
Find an Asymptotic bound on T.

We guess the solution is O (n (logn)).Thus for constant 'c'.
T (n) ≤c n logn
Put this in given Recurrence Equation.
Now,
T (n) ≤2c(n/2)log(n/2)+n
≤cnlogn-cnlog2+n
=cn logn-n (clog2-1)
≤cn logn for (c≥1)
Thus T (n) = O (n logn).