CODEWITHSUNDEEP
algorithmruntimerecurrence
jzhangnu
jzhangnu

Reputation: 51

Analyze the runtime of following recurrence

a.T(n)=T(n/2)+n;T(1)=1

Since i know the runtime of T(n)=2T(n/2)+n is O(nlogn), I think the answer is O(n^2), but the correct answer is O(n)

b.T(n)=2T(n/2)+1;T(1)=1

Since i know the runtime of T(n)=2T(n/2)+n is O(logn), I think the answer is O(log n), but the correct answer is O(n)

I'm really confused, since T(n)='work per level' x 'number of levels'. I think the number of work level in b is O(logn).

Upvotes: 1

Views: 75

Answers (1)

user3235832
user3235832

Reputation:

Use a trick substitution

enter image description here

... if you see any terms like T(n / 2) etc.

a)

enter image description here

b)

enter image description here

Upvotes: 2

Related Questions