## Interview Question

Country: India

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

The order will be O(n).

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

T(n)=2T(n/2) + 2
T(n/2)=2T(n/4)+2
so T(n)=2(2T(n/4)+2)+2=4T(n/4) + 4+ 2
Similarly,T(n/4)=2T(n/8)+2
So T(n)=4(2T(n/8)+2)+4+2=8T(n/8)+8+4+2
hence,
T(n)=(2^k)T(n/2^k) +2^k + (2^k-1 )+ .. +2

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

You're missing the most important part: the conclusion. You need to say that you keep this recurrence going until you have T(1), so in your equality you want n / 2^k = 1, which implies n = 2^k or k = log base 2 of n. Substituting, you get T(n) = n *O(1) + n/2 +n4 +... = O(n) (by convergence of the sum of this series).

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

Master theorem

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

Recursion tree: cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html
=> O(n)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

assume n = 2^K (2 per power K);
g(k) = 2 g(k-1) + 2;
2g(k-1) = 2^2g(k-1) + 2^2;
-- == -- + --
-- = -- + --
2^(n-1)g(2) = 2^n g(1) + 2^n
------------------------------------------
g(k) = 2^n g(1) + 2+ 2^2 + ...... + 2^n

T(n) = 2^n T(2) + 2(2^n -1);

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

Something's wrong. You should be getting O(n).

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.