Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
What is the smallest value of n such that an algorithm whose running time is 100n^2 runs faster than an algorithm whose running time is 2^n on the same machine?
Hardik Vagadia
asked
in
Algorithms
Aug 2, 2015
retagged
Jun 30, 2022
by
makhdoom ghaya
1,883
views
0
votes
0
votes
algorithms
time-complexity
Hardik Vagadia
asked
in
Algorithms
Aug 2, 2015
retagged
Jun 30, 2022
by
makhdoom ghaya
by
Hardik Vagadia
1.9k
views
answer
comment
Follow
share this
share
1 comment
by
Prashant.
commented
Mar 21, 2018
reply
Follow
share this
100n
^{2}
< 2
^{n}
For n= 15, 100n
^{2}
run faster than 2
^{n }
i.e. 22500 < 32768
0
0
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
1
Answer
9
votes
9
votes
Best answer
At $n=14$, $2^n-100n^2 = 2^{14}-100*14^2 = -3216$
At $n=15$, $2^n-100n^2 = 2^{15}-100*15^2 = 10268$
So at $n=15$, $2^n$ becomes greater than $100n^2$
Happy Mittal
answered
Aug 2, 2015
selected
Aug 2, 2015
by
Arjun
by
Happy Mittal
comment
Follow
share this
2 Comments
by
Hardik Vagadia
commented
Aug 2, 2015
reply
Follow
share this
But this becomes a preety easier when we use C/C++.
are we allowed to do so in GATE :P ?
0
0
by
Happy Mittal
commented
Aug 2, 2015
reply
Follow
share this
No, just use calculator and a bit of binary search manually, I found it through that only.
1
1
Please
log in
or
register
to add a comment.
← Previous
Next →
← Previous in category
Next in category →
Related questions
0
votes
0
votes
0
answers
1
usdid
asked
in
Algorithms
Apr 16, 2022
149
views
a) what is the iterative equation showing the running time of the algorithm whose pseudocode is given below? b) What is this repeated equation in asymptotic notation using the Master's theorem. c) What is the same repeated equation in asymptotic notation using the recursion tree method.
usdid
asked
in
Algorithms
Apr 16, 2022
by
usdid
149
views
asymptotic-notations
time-complexity
algorithms
0
votes
0
votes
1
answer
2
radha gogia
asked
in
Algorithms
Mar 7, 2016
484
views
We are given n keys and an integer k such that 1<=k<=n.Give an efficient algo to find any one of the k smallest keys .
radha gogia
asked
in
Algorithms
Mar 7, 2016
by
radha gogia
484
views
algorithms
time-complexity
7
votes
7
votes
2
answers
3
radha gogia
asked
in
Algorithms
Jul 19, 2015
16,607
views
Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
radha gogia
asked
in
Algorithms
Jul 19, 2015
by
radha gogia
16.6k
views
algorithms
sorting
time-complexity
4
votes
4
votes
5
answers
4
worst_engineer
asked
in
Algorithms
Oct 8, 2015
13,822
views
The running time of an algorithm is given by T(n) = T(n-1) + T(n-2) - T(n-3) , if n>3
worst_engineer
asked
in
Algorithms
Oct 8, 2015
by
worst_engineer
13.8k
views
algorithms
time-complexity
recurrence-relation
test-series
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
Recruitment of Scientific Officers in the Department of Atomic Energy 2023
GATE CSE 2023 Paper & Analysis - Memory Based
From GATE to Australia
DRDO Previous Year Papers
From Rank 4200 to 64: My Journey to Success in GATE CSE Exam
Subjects
All categories
General Aptitude
(2.5k)
Engineering Mathematics
(9.3k)
Digital Logic
(3.3k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.6k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(649)
Exam Queries
(843)
Tier 1 Placement Questions
(17)
Job Queries
(75)
Projects
(9)
Unknown Category
(853)
Recent Blog Comments
Recommend test series??
pressman pdf/ geeksforgeeks
where to study software engineering for BARC
+1
1200/1000 = 1.2
Twitter
WhatsApp
Facebook
Reddit
LinkedIn
Email
Link Copied!
Copy