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
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
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
Question_bank
f(n)=O(g(n)) Which of the following is True? 2^f(n)=O(2^(g(n)) log(f(n))=O(log(g(n)) f(n)=O(f(n/2)) f(n)=O(f(n)^2)
asked
5 days
ago
in
Algorithms
by
Shivam Kasat
Junior
(
811
points)

26
views
algorithms
timecomplexity
asymptoticnotations
0
votes
0
answers
2
GATEBOOK
Please mention proper approach to solve similar questions
asked
Dec 7
in
Algorithms
by
pps121
Active
(
1.4k
points)

48
views
timecomplexity
algorithms
0
votes
0
answers
3
Time Complexity
What is the time Complexity of this program ? (Do give detailed Answer)
asked
Dec 4
in
Algorithms
by
Ashish Roy 1
(
111
points)

88
views
timecomplexity
algorithms
programminginc
0
votes
1
answer
4
Kth Largest element in MinHeap
What is the time complexity to find the Kth largest element in a MinHeap? Or equivalently, What is the time complexity to find Kth smallest element in MaxHeap?
asked
Dec 1
in
Algorithms
by
gmrishikumar
(
461
points)

57
views
algorithms
heap
binaryheap
timecomplexity
sorting
0
votes
1
answer
5
Ace TestSeries
What is the time complexity of T(n) = T(n/3) + T(n/9) +n?
asked
Nov 29
in
Algorithms
by
Nidhi Budhraja
(
203
points)

53
views
algorithms
testseries
timecomplexity
acetestseries
0
votes
0
answers
6
#SELF DOUBT
Prove dijkstra’s algorithm using Heap is O((n+E)logn) where n is no.of vertices and E is number of edges? Book : Fundamentals of Computer Algorithms By sahni page : 263
asked
Nov 28
in
Algorithms
by
OneZero
(
255
points)

10
views
dijkstrasalgorithm
timecomplexity
0
votes
0
answers
7
#time complexity
T(n)=4T(n/2)+n$^{2}\sqrt{2}$ T.C
asked
Nov 24
in
Algorithms
by
amit166
Junior
(
529
points)

41
views
timecomplexity
+1
vote
1
answer
8
How is the time Complexity of this problem O(n log log n)?
asked
Nov 22
in
Algorithms
by
gmrishikumar
(
461
points)

148
views
algorithms
timecomplexity
recurrence
programminginc
program
0
votes
1
answer
9
T(n) = sqrt(n) * T(sqrt(n)) + n
T(n) = sqrt(n) * T(sqrt(n)) + n Given solution is O(log log n). But my solution is O(n log log n). 'wolframalpha'' shows the answer same as mine. You can find the solution here. Can anyone confirm the solution and provide an explantion?
asked
Nov 22
in
Algorithms
by
gmrishikumar
(
461
points)

101
views
algorithms
recurrence
timecomplexity
recursion
0
votes
1
answer
10
Programming (Time Complexity)
What will be time complexity: main() { int sum=0; for(int bound=1;bound<=n;bound*=2) { for(int i=0;i<bound;i++) { for(j=0;j<n;j+=2) { sum+=j; } for(int j=1;j<n;j*=2) { sum*=j; } } } } I think every for loop is participating to find T.C. something*2 means why will it run upto $log n$ and not upto $\frac{n}{2}$
asked
Nov 21
in
Programming
by
srestha
Veteran
(
103k
points)

94
views
timecomplexity
0
votes
0
answers
11
Karumanchi
There is a singly linked list. We have a pointer to a particular node(it is not tail node). what is the time and space complexity required to delete this node? my approach is... As there is no previous pointer so we traverse the list from the starting to just ... complexity as O(n) and space complexity O(1). but in the book the time complexity is mentioned O(1) where am I going wrong?
asked
Nov 20
in
DS
by
aditi19
Active
(
2.1k
points)

35
views
timecomplexity
linkedlists
datastructure
0
votes
0
answers
12
recurrence relation
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused
asked
Nov 18
in
Algorithms
by
LavTheRawkstar
Active
(
5.2k
points)

57
views
relations
recurrence
algorithms
timecomplexity
recurrenceeqation
0
votes
0
answers
13
Time Complexity
How to solve the following recurrence relation? T(n) = T(n6) + n2 , n>7 T(n) = 1 , n<= 7
asked
Nov 17
in
Algorithms
by
garvit_vijai
(
149
points)

47
views
timecomplexity
asymptoticnotations
recurrence
algorithms
0
votes
0
answers
14
Self Doubt  Quick Sort
Consider the following inputs: 1) 2 2 2 2 2 2 2 2) 1 2 3 4 5 6 7 3) 7 6 5 4 3 2 1 In all three cases, the worstcase time complexity of quicksort is O(n2) My doubt is if I am taking the middle element as a pivot, ... ), right? Can someone explain how we are saying worstcase time complexity for these three cases is O(n2) irrespective of the selection of the pivot element?
asked
Nov 16
in
Algorithms
by
garvit_vijai
(
149
points)

27
views
algorithms
quicksort
timecomplexity
0
votes
1
answer
15
What is the value of T(n) for the given recurrence relation
asked
Nov 14
in
Algorithms
by
sripo
Junior
(
933
points)

69
views
recurrence
algorithms
timecomplexity
jest
0
votes
0
answers
16
Karumanchi
f(n)=$2^n$ g(n)=n! h(n)=$n^{logn}$ which one is true? A) f(n)=O(g(n)) and g(n)=O(h(n)) B) f(n)=$\Omega(g(n)))$ and g(n)=O(h(n)) C) g(n)=O(f(n)) and h(n)=O(f(n)) D) h(n)=O(f(n)) and g(n)=$\Omega(f(n))$
asked
Nov 6
in
Algorithms
by
aditi19
Active
(
2.1k
points)

50
views
algorithms
timecomplexity
0
votes
0
answers
17
Time Complexity for an infinite loop
What is the time complexity for infinite loops Question 1 what is T(n) for this case While(1) { a=a+b; } Question 2 for this case if(1) { for i to n a=a+b } else { for i to n for j to n a=a+b } Edit 2: Compiled the code ... ); return 0; } output I get is 8 6 which means the else case is never executed hence in worst case do we have to consider the else part.
asked
Nov 6
in
Algorithms
by
sripo
Junior
(
933
points)

48
views
algorithms
timecomplexity
asymptoticnotations
spacecomplexity
0
votes
2
answers
18
Karumanchi
asked
Nov 4
in
Algorithms
by
aditi19
Active
(
2.1k
points)

87
views
algorithms
timecomplexity
#recurrencerelations
0
votes
0
answers
19
Find the Time Complexity
Suppose, we have an array of n elements. find the time complexity to search two elements x, y such that: a) x+y < 100 b) x+y > 1000 Also, state the algorithm/approach for the same.
asked
Nov 4
in
Algorithms
by
Naveen Kumar 3
Active
(
2.8k
points)

73
views
algorithms
timecomplexity
0
votes
1
answer
20
time complexity of recursive program
What is the time complexity of the following code snippet? Assume "statement" takes $O(1)$ time. int x=0; int A(n) { statement; if(n==1)return 1; else { x + = 4A(n/2)+n^{2} return (x); } } $A)\theta(n^{2}logn)$ $B)\theta(logn)$ $C)\theta(n^{2})$ $D)\theta(nlogn)$
asked
Nov 3
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
20.2k
points)

59
views
algorithms
timecomplexity
0
votes
0
answers
21
Time complexity of the program
Consider the following function(n) { val=0; for i=1 to n { if(n<=10000) for j=1 to n for k=1 to n val = val + 1; else for j=1 to n val = val + 1; } } The running time of the above function can best be described by $T(n)=$____________ $A)\theta(n^{3}) $ $B)\theta(n^{2})$ $C)\theta(n)$ $D)\theta(1)$
asked
Nov 3
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
20.2k
points)

60
views
algorithms
time
timecomplexity
0
votes
0
answers
22
A is polynomially reducible to B
Let there be two problems $A$ and $B$ It has been proved that,$A<B$ i.e. $A$ is polynomially reducible to $B.$This polynomial reduction is carried out in time of $O(n).$The problem $B$ can be solved in $O(n^{3})$ time. what is the time taken to solve problem $'A'?$ $A)O(n)$ $A)O(n^{3})$ $A)O(2^{n})$ $D)$None of these
asked
Nov 3
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
20.2k
points)

34
views
algorithms
timecomplexity
0
votes
0
answers
23
Runnig time on algorithm
What is the smallest value of $n$ (where $n$ is a natural number) such that an algorithm whose running time is $100\sqrt{n}$ runs faster than an algorithm whose running time is $2^{\frac{n}{2}}$ on the same machine?
asked
Nov 1
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
20.2k
points)

31
views
algorithms
timecomplexity
0
votes
0
answers
24
Self doubt on Asymptotic Notations
The iterated logarithmic function is defined as: $logn=0;$ $if$ $n\leq1$ $(or)$ $logn=1+log(logn);$ $if$ $n>1$ Which of the following is/are $True?$ $(1)logn=O(log(logn))$ $(2)(logn)!=O(logn)$ $(3) logn)^{n}=O((logn)!)$ $A)(1)$ $and$ $(2)$only$ $B)(1) and (3) only $ $C)(2)$ $and$ $(3)$ $only $ $D)(1),(2)$ $and$ $(3) $
asked
Nov 1
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
20.2k
points)

23
views
algorithms
timecomplexity
0
votes
1
answer
25
Recurrence Relations
Given $T(n)=T(\frac{n}{4})+T(\frac{n}{2})+n^{2},$ then $A)T(n)=\theta(n^{3})$ $B)T(n)=\theta(n^{2}logn)$ $C)T(n)=\theta(n^{2})$ $D)T(n)=\theta(n^{3}logn)$
asked
Nov 1
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
20.2k
points)

46
views
algorithms
recurrencerelations
timecomplexity
+1
vote
1
answer
26
Asymptotic Notations
Consider the following statements: $(1)$ Any two functions $f,g$ are always comparable under big Oh,that is $f=O(g)$ or $g=O(f)$ $(2)$ If $f=O(g)$ and $f=O(h)$ then $g(n)=\theta(h)$ $A)$ $(1)$ is true $(2)$ is false $B)$ $(1)$ is false $(2)$ is true $C)$ Both are false $D)$ Both are true
asked
Nov 1
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
20.2k
points)

44
views
algorithms
asymptoticnotations
timecomplexity
growthrate
0
votes
1
answer
27
Karumanchi
what is the time complexity of function(int n) { if(n<=1) return; for(int i=1; i<n; i++) { printf("*"); } function(0.8n); } i'm getting O(nlogn base 5/4) using the recurrence relation method but in the book it's given O(n) $T(n)=T(\frac{4n}{5})+O(n)$
asked
Oct 31
in
Algorithms
by
aditi19
Active
(
2.1k
points)

80
views
algorithms
timecomplexity
#recurrencerelations
0
votes
0
answers
28
time complexity
What is the time complexity of fun()? int fun(int n) { int count = 0; for (int i = 0; i < n; i++) for (int j = i; j > 0; j) count = count + 1; return count; }
asked
Oct 30
in
Algorithms
by
suneetha
(
379
points)

46
views
timecomplexity
0
votes
1
answer
29
time complexity
for(i=1;i<=n;++i) { j=1; while(j<=n) j=2*j; for(k=1;k<=n;++k) c=c+1; } then what is the time complexity will be?
asked
Oct 30
in
Algorithms
by
suneetha
(
379
points)

54
views
timecomplexity
0
votes
0
answers
30
time complexity
i=n; while(i>0) { j=1; while(j<=n) { j=2*j; } i=i/2; } then what is the time complexity?
asked
Oct 30
in
Algorithms
by
suneetha
(
379
points)

34
views
timecomplexity
Page:
1
2
3
4
5
6
...
24
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
IIT HYDERABAD M.Tech (RA) 3Years Winter Session Interview experience
INDIAN AIR FORCE
GATE BOOK _ TEST SERIES DOUBT_
Visualizing complex C code
GATE Book Test Series
Follow @csegate
Gatecse
Recent questions tagged timecomplexity
Recent Blog Comments
Please elucidate this really important...
when will be the grand/full test added??
There is one more problem. Ppl who have...
44,284
questions
49,776
answers
164,290
comments
65,856
users