The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Lists
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged timecomplexity
0
votes
0
answers
1
homework
I need to find the tight bound of the Fibonacci sequence in dynamic programming (using theta). I only know the bound using big O is O(n). Any idea how to do it?
asked
Oct 10
in
Algorithms
by
Mariela Prasetyo
(
13
points)

18
views
dynamicprogramming
timecomplexity
+1
vote
0
answers
2
radix sort counting sort
Given an array where numbers are in range from 1 to n6, which sorting algorithm can be used to sort these number in linear time? 1)Counting Sort 2)Radix Sort 3)Bubble Sort 4)Merge Sort.
asked
Oct 9
in
Algorithms
by
Kaushal Sanadhya
(
61
points)

33
views
algorithms
sorting
timecomplexity
radix
0
votes
0
answers
3
Merge Sort Doubt
what is the recurrence relation for merge sort?
asked
Oct 6
in
Algorithms
by
aditi19
Junior
(
849
points)

24
views
mergesort
algorithms
timecomplexity
#recurrencerelations
sorting
divideandconquer
+1
vote
3
answers
4
recurrence relation MIT
$T(n)=\sqrt{n} T(\sqrt{n})+100n$ Please solve this.
asked
Oct 4
in
Algorithms
by
sushmita
Boss
(
14.6k
points)

63
views
recurrence
algorithms
timecomplexity
recurrenceeqation
discretemathematics
0
votes
0
answers
5
Prove that for any constant c > 0, (log n)^c = o(n).
asked
Oct 3
in
Algorithms
by
Ojamajo Conan
(
35
points)

9
views
algorithms
timecomplexity
0
votes
1
answer
6
time complexity
If both of the algorithms A and B need O(nlogn) time then they both are equally efficient and finish in same amount of time. TRUE OR FALSE
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
14.6k
points)

60
views
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
7
MIT assignment
Find the complexity of the following code fragment: int i = 1; for(; i <= n logn; i + +) { for(i + +; i <= n; i + +) { print(1) } }
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
14.6k
points)

76
views
timecomplexity
asymptoticnotations
algorithms
0
votes
2
answers
8
Can we solve the recurrence T(n) = T(n/2) + 2^n by masters theorem, if possible?
asked
Sep 28
in
Algorithms
by
mohitrai0_0
(
157
points)

49
views
recurrence
algorithms
mastertheorem
timecomplexity
asymptoticnotations
+1
vote
1
answer
9
MIT ASSIGNMENT
Find the complexity of the following function when called with some integer n: void foo(n) { int i,j,k,x=0; for (i=1 ; i ≤ n ; i++) for (j=1 ; j ≤ i * i ; j++) { for ( k = 1 ; k ≤ j ; k++) { x=x+10; } }
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
14.6k
points)

75
views
algorithms
timecomplexity
asymptoticnotations
0
votes
1
answer
10
MIT ASSIGNMENT
FIND THE TIME COMPLEXITY int i=1,j; for(;i <= n;i + +) { for(j = i; j <= nlogn; j∗ = 2) { sum + +; } }
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
14.6k
points)

48
views
algorithms
timecomplexity
asymptoticnotations
0
votes
1
answer
11
MIT assigment
Arrange the following functions in their increasing order of complexities. $f(n) = n ^{0.999999} * logn$ ($log n$ is not in power) $g(n) = 10000 n$ $h(n) = n^{2}$ $k(n) = (1.000001)^{n}$ $p(n) = \frac{2 ^{√n}}{ n^{2}}$ $q(n) = \frac{n^{1.000001}}{logn}$
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
14.6k
points)

118
views
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
12
mit assignment
State true/false f(n) != O(g(n)) and g(n) != O(f(n))
asked
Sep 28
in
Algorithms
by
sushmita
Boss
(
14.6k
points)

31
views
algorithms
timecomplexity
asymptoticnotations
0
votes
0
answers
13
Cormen
Let $T$ be a minimum weight spanning tree of graph $G = (V, E)$, and let $V’$ be a subset of $V$ . Let $T'$ be a subgraph of $T$ induced by $V'$ and let $G’$ be a subgraph of $G$ induced by $V'$. Prove that If $T'$ is connected , then $T'$ is a minimum weight spanning tree of graph $G′$
asked
Sep 27
in
Algorithms
by
sushmita
Boss
(
14.6k
points)

34
views
algorithms
timecomplexity
minimumspanningtrees
0
votes
2
answers
14
Self doubt
Find the Complexity of: T(N) = T(${\sqrt{N}}$) + NlogN
asked
Sep 24
in
Algorithms
by
Sirjanpreet Singh Ba
(
7
points)

43
views
timecomplexity
algorithms
0
votes
0
answers
15
Solving recurrence relation by substitution method
asked
Sep 24
in
Compiler Design
by
GateAspirant999
Active
(
2.7k
points)

11
views
#recurrencerelations
timecomplexity
#agorithms
0
votes
0
answers
16
Cormen Appendix A
Why does (1/3+1/c) <=1?
asked
Sep 22
in
Algorithms
by
Noddy
(
27
points)

12
views
algorithms
asymptoticnotations
timecomplexity
0
votes
1
answer
17
Asymptoticnotations
f(n)=2(log2 n)2 , g(n)=log2n+1 How to give relation between them?.
asked
Sep 22
in
Algorithms
by
Vishnathan
(
189
points)

32
views
timecomplexity
asymptoticnotations
0
votes
0
answers
18
Quick Sort Analysis
Consider the Quicksort algorithm.Suppose there is a procedure for finding a pivot element which splits the list into two sublists each of which contains at least onefifth of the elements.Let T(n) be the number of comparisons required to sort n elements.Then: A. T(n)<=2T(n/5)+n B. T(n)<=T(n/5)+T(4n/5)+n C. T(n)<=2T(4n/5)+n D. T(n)<=2T(n/2)+n
asked
Sep 21
in
Algorithms
by
Vaishnavi01
(
153
points)

54
views
quicksort
algorithms
sorting
timecomplexity
gate
0
votes
1
answer
19
timecomplexcity
for(i=0;i<n;i++) for(j=0;j<i;j++) for(k=0;k<j;k++) what is the time complexity of above psudo code? explain.
asked
Sep 21
in
Algorithms
by
balaganesh
(
125
points)

39
views
timecomplexity
algorithms
asymptoticnotations
0
votes
0
answers
20
Algorithms Complexity
asked
Sep 21
in
Algorithms
by
Vaishnavi01
(
153
points)

80
views
algorithms
timecomplexity
asymptoticnotations
0
votes
1
answer
21
conceptual doubt
WHAT IS THE TIME COMPLEXITY TO ENQUEUE AN ELEMENT IF THE QUEUE IS IMPLEMENTED AS A CIRCULAR QUEUE AND WE HAVE GOT ONLY ONE POINTER TO FRONT ELEMENT??
asked
Sep 20
in
DS
by
sushmita
Boss
(
14.6k
points)

82
views
datastructure
linkedlists
timecomplexity
queues
0
votes
1
answer
22
Time complexity of code given
asked
Sep 17
in
Algorithms
by
GateAspirant999
Active
(
2.7k
points)

48
views
#time
timecomplexity
asymptoticnotations
0
votes
0
answers
23
Time complexity of given code using "finite" geometric series
asked
Sep 15
in
Mathematical Logic
by
GateAspirant999
Active
(
2.7k
points)

9
views
timecomplexity
algorithms
0
votes
1
answer
24
Verification of the Time Complexities
Can someone please validate the following respective time complexities?
asked
Sep 13
in
Algorithms
by
chauhansunil20th
Junior
(
505
points)

25
views
algorithms
timecomplexity
recurrence
0
votes
1
answer
25
TESTBOOK TEST SERIES
asked
Sep 12
in
Algorithms
by
Avik Chowdhury
Junior
(
827
points)

64
views
timecomplexity
0
votes
1
answer
26
class book
C function let n>=m. int gcd(n,m) { if(n%m==0) return m; n=n%m; return gcd(m,n); } time complexity
asked
Sep 11
in
Algorithms
by
amit166
(
211
points)

24
views
#time
timecomplexity
0
votes
2
answers
27
class notes
find time complexity f(int n){ int i=1; while(i<n) { int j=n; while(j>0) j=j/2; i=i*2; } }
asked
Sep 11
in
Algorithms
by
amit166
(
211
points)

23
views
timecomplexity
0
votes
1
answer
28
gatebook
Q2. int A(int) { if(n<=2) return 1; else return (A(√n)+n); } time complexity
asked
Sep 11
in
Algorithms
by
amit166
(
211
points)

18
views
timecomplexity
0
votes
1
answer
29
gatebook
Q.1 int A(int n){ if(n==2) return 1; else{ for(int j=1;j<=n;j++) printf(" * "); return(A(√n)); } } Time complexity
asked
Sep 11
in
Algorithms
by
amit166
(
211
points)

16
views
timecomplexity
0
votes
0
answers
30
Time Complexity
Please help with the following in Time Complexity. 1)Show that the following orderofmagnitude results hold: a)3n=O(n!) b)(n3 2n)/(n+1)=theta(n2) c)n3 /log(n+1)=O(n3) but not O(n2) 2)What is wrong with the following argument? x=O(n4),y=O(n2),therefore x/y=O(n2). 3) What is ... the following argument? f(n)=O(n2)+O(n), so that f(n)g(n)=O(n2 )+O(n)O(n2). Therefore, f(n)g(n)=O(n)
asked
Sep 10
in
Algorithms
by
Devshree Dubey
Boss
(
13.6k
points)

39
views
timecomplexity
algorithms
asymptoticnotations
Page:
1
2
3
4
5
6
...
23
next »
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
List of Available Exams
New Assignment on Network programming : P2P simulation
Theory of Computation  GO Classroom
Probability  GO Classroom
Daily Quiz
Follow @csegate
Gatecse
Recent questions tagged timecomplexity
Recent Blog Comments
You may contact FedEx local delivery office. It...
Yes you are right, it's showing this status from...
FedEx delivery is shown and as per that it is out...
that's my order ID: 40482491812380354
I have no control over Amazon fulfilled orders....
40,856
questions
47,522
answers
145,899
comments
62,280
users