NIELIT 2016 DEC Scientist B (CS) - Section B: 27

Question

What is the solution to the recurrence $T(n)=T \bigg (\dfrac{n}{2} \bigg )+n$?

• A. $O(\log n)$
• B. $O(n)$
• C. $O(n\log n)$
• D. None of these

Comments

No base case given. Assume for (n<=1) T(n) = 1.

Answer 1

O(n)----option B

simply apply master theorem and compare here ,

a=1,b=2

then ,, compare n^logba----->put a and b value get 1 ,,,right side fuction is already 'n'  so n is bigger so the answer will be O(n)