The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register
|
I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recurrence relation and Time Complexity
[closed]
0
votes
194
views
What is the time complexity of the following recurrence relation and step to derive the same
$T(n) = T(\sqrt{n}) + log(logn)$
closed with the note:
Query resolved.
time-complexity
algorithms
recurrence
recurrence-eqation
asked
Jan 20
in
Algorithms
by
VikramRB
(
239
points)
closed
Jan 21
by
VikramRB
|
194
views
comment
Please
log in
or
register
to add a comment.
1
Answer
+3
votes
Take $n=2^m$ then
$T(2^m)=T(2^{m/2})+\log m$
$\implies S(m)=S(m/2)+\log m$
Solve using master's theorem .$S(m)=O(\log ^2 m)=T(2^m)$
Put $m=logn \implies T(n)=(\log \log n)^2$
answered
Jan 20
by
Verma Ashish
Boss
(
11.8k
points)
comment
0
How did you derive the 3rd step, m = $2^{m}$ is understod but how $2^{m/2}$ written as m/2
+1
We are not replacing $2^m \;by\; m$ but we are changing function T to S.
$T(2^m)\implies$ function of m. (S(m))
$T(2^{m/2})\implies$ function of m/2. (S(m/2))
0
can you please tell me $log^2(logn)$ and $(loglogn)^2$both are same??
0
Yes..same
Please
log in
or
register
to add a comment.
← Prev. Qn. in Sub.
Next Qn. in Sub. →
← Prev.
Next →
Related questions
+3
votes
1
answer
1
time complexity to solve recurrence relation
recurrence relation for the functional value of F(n) is given below : $F(n) = a_{1}F(n-1) + a_{2}F(n-2) + a_{3}F(n-3) + ....... + a_{k}F(n-k)$ where $a_{i} =$ non zero constant. Best time complexity to compute F(n) ? assume k base values starting from F( ... ( $O(k_{2}r^{k_{1}n})$) B. Linear ( $O(n)$ ) C. Logarithmic ( $O(\log n)$ ) D. $O(n \log n)$
asked
Aug 11, 2016
in
Algorithms
by
dd
Veteran
(
57k
points)
|
511
views
algorithms
recurrence
time-complexity
recurrence-eqation
+3
votes
1
answer
2
Time Complexity for Recurrence relation
What will be the time complexity for the following recurrence relation? $T(n) = 8\sqrt{n} T(\sqrt{n})+(log n)^{2}$ According to me it is $\Theta (n(logn)^{3})$ . Please confirm.
asked
Jun 16, 2017
in
Algorithms
by
Ashish Sharma 3
(
343
points)
|
473
views
time-complexity
recurrence
recurrence-eqation
master-theorem
0
votes
1
answer
3
Recurrence relation
T(n) = T(n/4) + T(3n/4) + n How to solve these type of problems? Can I solve this using master theorm by considering X = T(3N/4) +N THEN T(N) = T(N/4) +X CAN WE SOLVE LIKE THIS? PLEASE HELP
asked
Jan 4
in
Algorithms
by
Mayankprakash
Junior
(
997
points)
|
186
views
recurrence-eqation
time-complexity
recurrence
algorithms
0
votes
0
answers
4
recurrence relation
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused
asked
Nov 18, 2018
in
Algorithms
by
LavTheRawkstar
Active
(
3.7k
points)
|
136
views
relations
recurrence
algorithms
time-complexity
recurrence-eqation
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
Recent Posts
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
All categories
General Aptitude
1.9k
Engineering Mathematics
7.5k
Digital Logic
2.9k
Programming and DS
4.9k
Algorithms
4.3k
Theory of Computation
6.2k
Compiler Design
2.1k
Operating System
4.5k
Databases
4.1k
CO and Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.5k
Others
1.5k
Admissions
595
Exam Queries
576
Tier 1 Placement Questions
23
Job Queries
72
Projects
17
Follow @csegate
Recent Blog Comments
It's a question not a post..
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
bro can be upload all standard book questions in...
50,647
questions
56,479
answers
195,421
comments
100,553
users