## Interview Question

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a problem to solve the complexity of an recursive algorithm.

I can be solved using the Master Theorem

for the complexity: T(n)=2T(n/2)+n

the general expression is T(n)=aT(n/b)+f(n), where f(n)=Theta(n^c*log^k n)

That means:
a=2,b=2
f(n)=Theta(n^1*log^0n)
c=1, k=0

log_a (b)= log_2 (2)=1 and at the same time c=1

That means it is case 2 of the Master theorem, then
T(n)=Theta(n^c* log_k+1(n))=Theta(n^1 * log_0_1 (n))=Theta(n*log(n)).

This is for example merge sort

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.