edited by
2,790 views
3 votes
3 votes

The recurrence relation $T(n) =mT(\frac{n}{2}) + tan^2$ is satisfied by

  1. O(n$^2$)
  2. O(n$^{lg \, m}$)
  3. O(n$^2 \: lg \:n)$
  4. O(n lg n)
edited by

2 Answers

7 votes
7 votes



Now according to Master Theorem a=m , b=2 and f(n)=an2

nlog2m > f(n) for all m>4    [Using case-1:  Master Theorem]


so solution is O(nlog2m)  

Ans : B

Note :  inplace of  

Answer:

Related questions

2 votes
2 votes
1 answer
1
go_editor asked Jul 28, 2016
2,425 views
Let $A$ and $B$ be two $n$ $\times$$n$ matrices. The efficient algorithm to multiply the two matrices has the time complexity$O(n^3)$$O(n^{2.81})$$O(n^{2.67})$$O(n^2)$
2 votes
2 votes
2 answers
2
go_editor asked Jul 28, 2016
1,951 views
Assuming there are n keys and each key is in the range [0, m-1]. The run time of bucket sort isO(n)O(n lgn)O(n lgm)O(n+m)
3 votes
3 votes
2 answers
3
go_editor asked Jul 28, 2016
5,628 views
The longest common subsequence of the sequences $X=<A, B, C, B, D, A, B>$ and $Y=<B, D, C, A, B, A>$ has length$2$$3$$4$$5$
3 votes
3 votes
2 answers
4