The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
0
votes
149
views
what is the recurrence relation for binary search and linear search?
please explain how to derive them.
recurrence
algorithms
timecomplexity
recurrenceeqation
discretemathematics
asked
Jan 11, 2018
in
Algorithms
by
iarnav
Loyal

149
views
answer
comment
0
$T(n)=T(\frac{n}{2})+1$ for binary search
$T(n)=T(n1) +1$ for linear search.
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
1
Answer
+2
votes
Best answer
For binary search:
For Linear Search:
answered
Jul 18, 2018
by
mohitjarvissharma
selected
Jul 18, 2018
by
iarnav
comment
Please
log in
or
register
to add a comment.
← Prev.
Next →
← Prev. Qn. in Sub.
Next Qn. in Sub. →
Related questions
+4
votes
3
answers
1
recurrence relation MIT
$T(n)=\sqrt{n} T(\sqrt{n})+100n$ Please solve this.
asked
Oct 4, 2018
in
Algorithms
by
sushmita
Boss

379
views
recurrence
algorithms
timecomplexity
recurrenceeqation
discretemathematics
0
votes
1
answer
2
Recurrence relation and Time Complexity
What is the time complexity of the following recurrence relation and step to derive the same $T(n) = T(\sqrt{n}) + log(logn)$
asked
Jan 20, 2019
in
Algorithms
by
VikramRB

289
views
timecomplexity
algorithms
recurrence
recurrenceeqation
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, 2019
in
Algorithms
by
Mayankprakash
Junior

241
views
recurrenceeqation
timecomplexity
recurrence
algorithms
0
votes
1
answer
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

205
views
relations
recurrence
algorithms
timecomplexity
recurrenceeqation
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
GATE Overflow Test Series  GATE CSE 2021
IIT gandhinagar mtech cse2020
IIT Delhi Research Interview Shortlists out
IIT Gandhinagar interview experience
IIT Gandhinagar Interview 2020
Subjects
All categories
General Aptitude
1.9k
Engineering Mathematics
8.2k
Digital Logic
2.9k
Programming and DS
5k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.2k
Operating System
4.6k
Databases
4.2k
CO and Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.2k
Others
1.5k
Admissions
595
Exam Queries
562
Tier 1 Placement Questions
23
Job Queries
71
Projects
19
Unknown Category
1k
Recent Blog Comments
Verification will automatically expire after 400...
My Verification is showing as "Not verified Yet"...
The point calculation formula is changed. We were...
Keep doing problems. Chances are high that you...
The price will be the same till June 30th.
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,215
questions
60,009
answers
201,234
comments
94,696
users