Register

Find time complexity :

269 views

1 Answer

Best answer
2 votes
2 votes

use master theorem we will get answer as 

nlog21    

  = n0 = 1 (i.e constant)

so time complexity will be ⊜(n)

Or,

T(n) = n + n/2 + n/4 + n/8 + ..... + 1.

       =2n

       = O(n)

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

3 votes
3 votes
1 answer
1
sumit_kumar asked Jun 25, 2017
3,150 views
find recursive time complexity of fibonacci series by substitution method
what is time comlexity procedure for following recursive equation by substitution method: T(n)= T(n-1)+T(n-2) , if n>=2 =1 , if n=1; =0 , if n=0.
what is time comlexity procedure for following recursive equation by substitution method:T(n)= T(n-1)+T(n-2) , if n>=2 =1 , if n=1; =0 , if n=0.
User Avatar
2 votes
2 votes
1 answer
2
Akriti sood asked Jan 23, 2017
779 views
find the time complexity|testbook livetest
please tell the time complexity?i was getting O(2n)
please tell the time complexity?i was getting O(2n)
User Avatar
2 votes
2 votes
1 answer
3
sh!va asked Jul 12, 2016
555 views
Find the complexity of recurrence equation:
A scientist developed a new algorithm for computation and he observed that ot follows the recurrence equation as $T(n) = \begin{cases} 2T(n-1) -1 & \quad if\: n>0 \\ 1 & \quad otherwise \end{cases}$ What is the complexity of new algorithm? $2^n$ $2^{n+1}$ $2^{n-1}$ None of these
A scientist developed a new algorithm for computation and he observed that ot follows the recurrence equation as$T(n) = \begin{cases} 2T(n-1) -1 & \quad if\: n>0 \\ 1 & ...
User Avatar
14 votes
14 votes
5 answers
4
Jonathan Decosta asked Jun 10, 2015
47,297 views
How to find the complexity of T(n)=T(sqrt(n)) + 1 ?
Please tell me the complete steps how to solve this problem. $ T(n) = T ( \sqrt n )+ 1$
Please tell me the complete steps how to solve this problem.$ T(n) = T ( \sqrt n )+ 1$
User Avatar
Link Copied!