menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
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
Update on GO Book for GATE 2022
Barc Interview Experience 2020- CSE stream
JEST 2021 registrations are open
TIFR GS-2021 Online Application portal
IIT Jodhpur Mtech AI - Interview Expierence (Summer Admission)
Subjects
All categories
General Aptitude
(2.1k)
Engineering Mathematics
(8.5k)
Digital Logic
(3k)
Programming and DS
(5.1k)
Algorithms
(4.5k)
Theory of Computation
(6.3k)
Compiler Design
(2.2k)
Operating System
(4.7k)
Databases
(4.3k)
CO and Architecture
(3.5k)
Computer Networks
(4.3k)
Non GATE
(1.2k)
Others
(1.3k)
Admissions
(595)
Exam Queries
(838)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(1.1k)
Recent Blog Comments
Ohh, yeah now turned off. Got it sir, Thank you :)
I guess you might have turn on "Only GATE...
https://gateoverflow.in/280484/tifr2019-b-11 Arju...
Which question disappeared? Can you share a link?
OFFTOPIC:- @Arjun sir why are the questions of...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Recurrence relation and Time Complexity
[closed]
0
votes
428
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, 2019
in
Algorithms
VikramRB
closed
Jan 21, 2019
by
VikramRB
428
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, 2019
Verma Ashish
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.
Next →
← Prev. Qn. in Sub.
Next Qn. in Sub. →
Related questions
3
votes
1
answer
1
983
views
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)$
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} =$ ... $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
dd
983
views
algorithms
recurrence
time-complexity
recurrence-eqation
3
votes
1
answer
2
694
views
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.
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
Ashish Sharma 3
694
views
time-complexity
recurrence
recurrence-eqation
master-theorem
0
votes
1
answer
3
418
views
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
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, 2019
in
Algorithms
Mayankprakash
418
views
recurrence-eqation
time-complexity
recurrence
algorithms
0
votes
1
answer
4
309
views
recurrence relation
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused
asked
Nov 18, 2018
in
Algorithms
LavTheRawkstar
309
views
relations
recurrence
algorithms
time-complexity
recurrence-eqation
...