The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook 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 spacecomplexity
0
votes
0
answers
1
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, 2018
in
Algorithms
by
sripo
Active
(
1.5k
points)

91
views
algorithms
timecomplexity
asymptoticnotations
spacecomplexity
+2
votes
2
answers
2
Test Algorithms
What is the space complexity of the following code? $O(logn)$ $O(n)$ $O(nlogn)$ $O(1)$
asked
Aug 17, 2018
in
Algorithms
by
Shivani gaikawad
Junior
(
769
points)

88
views
algorithms
spacecomplexity
0
votes
1
answer
3
Space Complexity of Dijkastra's algorithm
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithmspacetimecomplexity) But how ????
asked
Jul 5, 2018
in
Algorithms
by
Hardik Maheshwari
(
113
points)

334
views
dijkstrasalgorithm
shortestpath
spacecomplexity
algorithms
graphalgorithms
greedyalgorithm
0
votes
0
answers
4
#Algorithms Space Complexity Vs Auxiliary Space Complexity?
I'm kind of confused between these two terms as for example  the Auxiliary space of merge sort, heapsort and insertion sort is O(1) whereas Space complexity of merge sort, insertion sort, heapsort is O(n). So, if someone ... ? Furthermore I know  Space Complexity = Auxiliary Space + space taken by also wrt input. Kindly help, thank you!
asked
Jun 26, 2018
in
Algorithms
by
iarnav
Loyal
(
9.6k
points)

68
views
algorithms
spacecomplexity
0
votes
1
answer
5
Space Complexity of Build Max Heap
Since Heapify is a recursive function, its space complexity is $O(logn)$ because of the stack space required for recursion. I also read that space complexity of heapsort is $O(1)$ beause of the explanation here  https://gateoverflow.in/79909/ ... complexity of build heap is $O(logn)$ then heapsorts complexity should also be the same . What am I missing here ?
asked
Jun 14, 2018
in
Algorithms
by
Hardik Maheshwari
(
113
points)

186
views
spacecomplexity
comlexity
algorithms
heap
heapsort
0
votes
1
answer
6
Evaluation of Postfix expression using stack
What is time and space complexity to evaluate postfix expression ?
asked
May 6, 2018
in
DS
by
JaiKumar Guwalani
(
11
points)

344
views
datastructure
timecomplexity
spacecomplexity
infixpostfix
stack
0
votes
1
answer
7
Space complexity of Huffman coding
what is Space complexity of Huffman coding?
asked
Apr 26, 2018
in
Algorithms
by
Akash Kumar Roy
Junior
(
527
points)

297
views
huffmancode
algorithms
spacecomplexity
explainable_answer
0
votes
2
answers
8
MY DOUBT: Worst case space complexity of Quick sort (NOT FOR A STRAIGHT ANSWER)
First read it properly. I am not asking a specific question about space complexity. Question: What is worst case space complexity of quick sort? Everywhere it is showing O(logn). My understanding about it: I know that Quick ... done by ratio 1:n1 which is worst case, wouldn't it be requesting for O(n) stack records?
asked
Apr 21, 2018
in
DS
by
Akash Kumar Roy
Junior
(
527
points)

178
views
algorithms
sorting
datastructure
spacecomplexity
+1
vote
0
answers
9
How large can the ratio of two memory requirements get?
Sartaj Sahani Chapter 7 question 9 I seem to have stumbled upon something very basic, and I can't figure out why. The question asks "How large can the ratio of two memory requirements get?" when a 2D Array is stored as a 2d array in c++ and when ... 4m) / (4mn) = 1 + 4/n. Shouldn't it be 1 +1/n ? Can anyone help me out here ? Thanks.
asked
Mar 3, 2018
in
DS
by
XbrucewayneX
(
111
points)

103
views
datastructure
arrays
spacecomplexity
+3
votes
1
answer
10
Algorithms
I am having a doubt in this question. The binary search algorithm is implemented using recursion. Then the space complexity is : (1) O( 1 ) (2) O( n ) (3) O( logn ) (4) O(n logn ) According to me, the answer should be option 2. Please explain the solution as well.
asked
Jan 12, 2018
in
Programming
by
Asim Abbas
(
225
points)

108
views
algorithms
spacecomplexity
+3
votes
2
answers
11
Space complexity
Worst case and best case space complexity of merge sort is ___________________________
asked
Nov 11, 2017
in
Algorithms
by
srestha
Veteran
(
109k
points)

102
views
algorithms
spacecomplexity
+2
votes
1
answer
12
How to determine the time complexity of this loop?
// func() is any constant root function for (int i = n; i > 0; i = func(i)) { // some O(1) expressions or statements } "In this case, i takes values n, n1/k, (n1/k)1/k = n1/k2, ... do we calculate that there are logk(log(n)) iterations? Source: http://www.geeksforgeeks.org/timecomplexitylooploopvariableexpandsshrinksexponentially/
asked
Nov 7, 2017
in
Algorithms
by
Narasimhan
(
125
points)

290
views
algorithms
asymptoticnotations
timecomplexity
spacecomplexity
nongate
+5
votes
1
answer
13
Inplace Merge Sort via Doubly linked list in place of Array
In general merge sort is not considered inplace sorting technique. Because an auxiliary array is used. If we will try to do it inplace in array data structure then our merge procedure will take O($n^2$) time. so overall ... list in place of Array (for storing and merging data) ? Please share your valuable opinion. It will be great help.
asked
Nov 2, 2017
in
Algorithms
by
Chhotu
Boss
(
12.4k
points)

246
views
algorithms
sorting
spacecomplexity
linkedlists
timecomplexity
+2
votes
1
answer
14
Gatebook_Mocktest2(DS)
The intended purpose of this code is to precompute all the primes less than N. When it is finished executing, for r ∈ [2, N), bits[r] is supposed to equal 1 if and only if N is composite. Assume that the bits array is initialized to all zeroes. for ( int x = 2; x < N ... a natural number n < N is prime. (A) I only (B) I and II only (C) II and III only (D) I, II, and III
asked
Feb 8, 2017
in
DS
by
smartmeet
Active
(
5.2k
points)

205
views
gatebook_mt2
datastructure
spacecomplexity
timecomplexity
asymptoticnotations
0
votes
0
answers
15
GateBook Mock Test_2(Algorithms)
The intended purpose of this code is to precompute all the primes less than N. When it is finished executing, for r ∈ [2, N), bits[r] is supposed to equal 1 if and only if N is composite. Assume that the bits array is initialized to all zeroes. for ( int x = 2; x ... number n < N is prime. (A) I only (B) I and II only (C) II and III only (D) I, II, and III
asked
Feb 7, 2017
in
Algorithms
by
smartmeet
Active
(
5.2k
points)

172
views
gatebook_mt2
datastructure
algorithms
spacecomplexity
timecomplexity
0
votes
1
answer
16
Space complexity
Which of the following algorithm have the smallest memory requirement i.e Low space complexity including data space and run time stack for recursive calls. A)insertion sort B)quick sort C)merge sort D)selection sort
asked
Feb 5, 2017
in
Programming
by
reena_kandari
Loyal
(
8.4k
points)

288
views
algorithms
spacecomplexity
sorting
+3
votes
1
answer
17
Project Euler Problem 1
What is the Time and Space Complexity of Both the Codes ? Are both O(1)? If so why? And then how is the second more efficient? Below is the code in Brute Force for(i=0;i<1000;i++) { if(i%3==0  i%5==0) { sum+=i; } } This is Using Summation int P1(int n) { int t,x,f; t=(n1)/3; x=(n1)/5; f=(n1)/15; return((3*t*(t+1)/2) + (5*x*(x+1)/2)  (15*f*(f+1)/2)); }
asked
Jan 28, 2017
in
Algorithms
by
sripo
Active
(
1.5k
points)

116
views
algorithms
timecomplexity
spacecomplexity
0
votes
0
answers
18
Algorithms [Euclid's Algorithm for GCD]
What is the best case and worst case time complexity for Euclid's algorithm?Let numbers be a and b As per my understanding Best case  If a and b are multiple :0(1). Worst case  Both are consecutive fibonicci number.Complexity?
asked
Dec 8, 2016
in
Algorithms
by
rahul sharma 5
Boss
(
26.8k
points)

255
views
algorithms
spacecomplexity
+5
votes
2
answers
19
Space complexity of heap sort
Why space complexity of heapsort is O(1)....and why not O(logn)..because of space required by recursion calls which is equivalent to height of the tree...where am i getting wrong plz help...
asked
Nov 7, 2016
in
Algorithms
by
vineet.ildm
Active
(
1.1k
points)

1k
views
algorithms
timecomplexity
spacecomplexity
sorting
heap
+6
votes
2
answers
20
Test Series
Which algorithm has smallest memory requirement in terms of data space and runtime stack(for recursive calls)? (Low Space Complexity) A. Insertion sort B. Selection sort C. Quick Sort D. Merge Sort
asked
Nov 3, 2016
in
Algorithms
by
parthbkgadoya
(
383
points)

362
views
testseries
algorithms
sorting
spacecomplexity
+4
votes
1
answer
21
Space Complexity of sorting
asked
Oct 19, 2016
in
Algorithms
by
KISHALAY DAS
Loyal
(
6.6k
points)

463
views
spacecomplexity
algorithms
0
votes
1
answer
22
BFS Theory
1. Does space complexity includes both input space and extra space needed for algorithm or only extra space? 2.What will be Space complexity for BFS algorithm with adjacency matrix representation? Please reply with supporting references.
asked
Oct 12, 2016
in
Algorithms
by
Shyam Singh 1
Active
(
1.5k
points)

249
views
spacecomplexity
bfs
0
votes
2
answers
23
Find the Space complexity of following Code [Ace Gate Practice Booklet Vol1 Page 127]
asked
Jun 2, 2016
in
Algorithms
by
APOORV PANSE
(
181
points)

656
views
spacecomplexity
algorithms
+1
vote
1
answer
24
GEEK_MOCK_QUETION_14
QUESTION 14 : Consider the below Pseudo code written in C style bool fun(int arr[], int n, int X) { if (X == 0) return true; if (n == 0 && X != 0) return false; if (arr[n–1]*arr[n–1] > X) return fun(arr ... n) extra space D) Time Complexity of fun() is O(n2) and it requires O(n2) extra space Correct – A How to calculate space complexity?
asked
Jan 26, 2016
in
Algorithms
by
Sumit1311
Active
(
1.6k
points)

369
views
spacecomplexity
timecomplexity
geekmock2016
+5
votes
1
answer
25
What is the time complexity?
double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += foo(i); } return sum; } } The time complexity of the above code is?
asked
Aug 29, 2014
in
Algorithms
by
Arjun
Veteran
(
386k
points)

580
views
timecomplexity
spacecomplexity
algorithms
normal
To see more, click for the
full list of questions
or
popular tags
.
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 Gandhinagar review
Is DAIICT good for doing MTech ?
AIR175 : GO is enough
GATE 2019 My reasoned routine. (AIR 558)
if i can you also can
Follow @csegate
Recent questions tagged spacecomplexity
Recent Blog Comments
can i get a call on 580 (OBCNCL)
Many times Anger , Aggression and Fear push...
One word would be "Priorities" Second word shall...
What's interesting to me is that despite having...
Brother!! your all posts are really worth to read...
48,635
questions
52,769
answers
183,405
comments
68,308
users