Register

#recurrence

224 views
1 votes
1 votes

what is the difference between below two questions??

both seems to be same ,but why are they are having different time complexities?? i m really confused...plz help me

https://gateoverflow.in/1829/gate2006-51-isro2016-34

https://gateoverflow.in/841/gate2002-2-11

User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
aniketpatil32 asked May 11, 2019
222 views
#algorithms #recurrence-relation
T(n)=T(√n) + n I am finding it difficult to solve last step of this recurrence relation . Please help me with expansion of this recurrence relation.
T(n)=T(√n) + n I am finding it difficult to solve last step of this recurrence relation . Please help me with expansion of this recurrence relation.
User Avatar
3 votes
3 votes
2 answers
3
Atul Verma12 asked Dec 13, 2016
818 views
#recurrence relation
solve the recurrence relation: $T(n)=T(\sqrt{n})+\Theta (\log \log n)$ My first step was to let $m=\log ⁡n$, making the above: $T(2^m)=T(2^{\frac{m}{2}})+\Theta (\log m)$ Why we can say that $S(m)=T(2^{m})$ ? Please Explain the upcoming steps ?
solve the recurrence relation:$T(n)=T(\sqrt{n})+\Theta (\log \log n)$My first step was to let $m=\log ⁡n$, making the above:$T(2^m)=T(2^{\frac{m}{2}})+\Theta (\log m)$W...
User Avatar
4 votes
4 votes
7 answers
4
Anil Khatri asked Aug 31, 2016
8,929 views
#recurrence relation
Determine theta bound for recurrence : $T(n)=T(n/2)+T(n/4)+T(n/8)+n$
Determine theta bound for recurrence :$$T(n)=T(n/2)+T(n/4)+T(n/8)+n$$
User Avatar
Link Copied!