The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
570 views

Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$.

Which of the following statements is true?

  1. $T(n) = O \sqrt{n}$

  2. $T(n)=O(n)$

  3. $T(n) = O (\log n)$

  4. None of the above

asked in Algorithms by Veteran (59.5k points)
edited by | 570 views
0
How to do it by recurrence tree method?

1 Answer

+15 votes
Best answer

Answer is $B$.

using master method (case 1)

where a = 2, b = 2

O(n1/2) < O(nlogba)

O(n1/2) < O(nlog22)

answered by Loyal (9k points)
edited by
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,513 questions
46,665 answers
139,712 comments
57,486 users