edited by
4,793 views
21 votes
21 votes

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

edited by

1 Answer

Best answer
38 votes
38 votes

Answer is $B$.

using master method (case 1)

where a = 2, b = 2

O(n1/2) < O(nlogba)

O(n1/2) < O(nlog22)

edited by
Answer:

Related questions

11 votes
11 votes
5 answers
1
64 votes
64 votes
8 answers
2
Kathleen asked Sep 29, 2014
37,245 views
Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring?$0^*(1+0)^*$$0^*1010^*$$0^*1^*01^*$$...
21 votes
21 votes
3 answers
4
Kathleen asked Sep 29, 2014
4,973 views
The correct matching for the following pairs is$$\begin{array}{ll|ll}\hline \text{A.} & \text{All pairs shortest path} & \text{1.} & \text{Greedy} \\\hline \text{B.} & \...