menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
GO Book for GATECSE 2022
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
Exact tag match
Recent Posts
A Short Guide to GATE
Seeking DRDO Scientist B previous year papers
STRATEGY TO EFFECTIVELY CREATE SHORT & MICRO NOTES FOR GATE EXAM AND BEST REVISION STRATEGY BY AIR-"152"
My Video Experience AIR-152 GATE_CS(Some More motivation)!!!!!!
AIR 33 IN GATE 2021 AND HOW I USED GATEOVERFLOW DURING MY PREPARATION
Subjects
All categories
General Aptitude
(2.1k)
Engineering Mathematics
(8.5k)
Digital Logic
(3.1k)
Programming and DS
(5.2k)
Algorithms
(4.5k)
Theory of Computation
(6.3k)
Compiler Design
(2.2k)
Operating System
(4.7k)
Databases
(4.3k)
CO and Architecture
(3.5k)
Computer Networks
(4.3k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(838)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(1.1k)
Follow @gateoverflow
GATE Overflow
Recent questions tagged space-complexity
Recent Blog Comments
A Wonderful journey and a Great compilation of...
@hitchh1ker Thank You :) I will share TOC and...
may i know ur emailID ...just want to ask few...
Congratulations !!π Were u preparing full...
Congrats and thanks for detailed guide.
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Recent questions tagged space-complexity
1
vote
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.
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 never goes to the else part ... %d",a,b); 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
sripo
834
views
algorithms
time-complexity
asymptotic-notations
space-complexity
5
votes
2
answers
2
Test Algorithms
What is the space complexity of the following code? $O(logn)$ $O(n)$ $O(nlogn)$ $O(1)$
What is the space complexity of the following code? $O(logn)$ $O(n)$ $O(nlogn)$ $O(1)$
asked
Aug 17, 2018
in
Algorithms
Shivani gaikawad
407
views
algorithms
space-complexity
1
vote
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/algorithm-space-time-complexity) But how ????
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????
asked
Jul 5, 2018
in
Algorithms
Hardik Maheshwari
1.6k
views
dijkstras-algorithm
shortest-path
space-complexity
algorithms
graph-algorithms
greedy-algorithm
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!
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 asks me what's the Space ... we mention auxiliary space? Furthermore I know - Space Complexity = Auxiliary Space + space taken by also wrt input. Kindly help, thank you!
asked
Jun 26, 2018
in
Algorithms
iarnav
275
views
algorithms
space-complexity
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 ?
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/space-complexity-of-heap-sort ... If space 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
Hardik Maheshwari
1.5k
views
space-complexity
algorithms
heap
heap-sort
1
vote
1
answer
6
Evaluation of Postfix expression using stack
What is time and space complexity to evaluate postfix expression ?
What is time and space complexity to evaluate postfix expression ?
asked
May 6, 2018
in
DS
JaiKumar Guwalani
947
views
data-structures
time-complexity
space-complexity
infix-prefix
stack
1
vote
2
answers
7
Space complexity of Huffman coding
what is Space complexity of Huffman coding?
what is Space complexity of Huffman coding?
asked
Apr 26, 2018
in
Algorithms
Akash Kumar Roy
1.3k
views
huffman-code
algorithms
space-complexity
explainable-answer
0
votes
3
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:n-1 which is worst case, wouldn't it be requesting for O(n) stack records?
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 sort algorithm doesn't request extra space except for ... if partition is being done by ratio 1:n-1 which is worst case, wouldn't it be requesting for O(n) stack records?
asked
Apr 21, 2018
in
DS
Akash Kumar Roy
1.2k
views
algorithms
sorting
data-structures
space-complexity
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.
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 stored as a 1D array by row major mapping. The ... is how (4mn + 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
XbrucewayneX
186
views
data-structures
arrays
space-complexity
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.
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
Asim Abbas
255
views
algorithms
space-complexity
3
votes
2
answers
11
Space complexity
Worst case and best case space complexity of merge sort is ___________________________
Worst case and best case space complexity of merge sort is ___________________________
asked
Nov 11, 2017
in
Algorithms
srestha
213
views
algorithms
space-complexity
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/time-complexity-loop-loop-variable-expands-shrinks-exponentially/
// 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, n1/k3, , n1/klogk(log(n)), so ... the above statement? How do we calculate that there are logk(log(n)) iterations? Source: http://www.geeksforgeeks.org/time-complexity-loop-loop-variable-expands-shrinks-exponentially/
asked
Nov 7, 2017
in
Algorithms
Narasimhan
614
views
algorithms
asymptotic-notations
time-complexity
space-complexity
non-gate
5
votes
1
answer
13
In-place Merge Sort via Doubly linked list in place of Array
In general merge sort is not considered in-place sorting technique. Because an auxiliary array is used. If we will try to do it in-place 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.
In general merge sort is not considered in-place sorting technique. Because an auxiliary array is used. If we will try to do it in-place in array data structure then our merge procedure will take O($n^2$ ... using a doubly linked 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
Chhotu
735
views
algorithms
sorting
space-complexity
linked-lists
time-complexity
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
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; x = x + 1 ... 1) time whether 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
smartmeet
282
views
gatebook-mt2
data-structures
space-complexity
time-complexity
asymptotic-notations
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
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; x = x + 1 ... 1) time whether 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 7, 2017
in
Algorithms
smartmeet
230
views
gatebook-mt2
data-structures
algorithms
space-complexity
time-complexity
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
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
reena_kandari
415
views
algorithms
space-complexity
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=(n-1)/3; x=(n-1)/5; f=(n-1)/15; return((3*t*(t+1)/2) + (5*x*(x+1)/2) - (15*f*(f+1)/2)); }
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=(n-1)/3; x=(n-1)/5; f=(n-1)/15; return((3*t*(t+1)/2) + (5*x*(x+1)/2) - (15*f*(f+1)/2)); }
asked
Jan 28, 2017
in
Algorithms
sripo
166
views
algorithms
time-complexity
space-complexity
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?
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
rahul sharma 5
467
views
algorithms
space-complexity
8
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...
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
vineet.ildm
2.7k
views
algorithms
time-complexity
space-complexity
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
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
parthbkgadoya
486
views
test-series
algorithms
sorting
space-complexity
4
votes
1
answer
21
Space Complexity of sorting
asked
Oct 19, 2016
in
Algorithms
KISHALAY DAS
624
views
space-complexity
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.
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
Shyam Singh 1
459
views
space-complexity
bfs
0
votes
1
answer
23
Online Question from a test
Which of the following algorithm has the smallest memory requirement, including data space and run time stack for recursive calls? A. Insertion Sort B. Quick Sort C. Selection Sort D. Merge Sort
Which of the following algorithm has the smallest memory requirement, including data space and run time stack for recursive calls? A. Insertion Sort B. Quick Sort C. Selection Sort D. Merge Sort
asked
Sep 2, 2016
in
Algorithms
parulnabi
268
views
space-complexity
algorithms
2
votes
3
answers
24
UGCNET-Dec2015-II: 39
An ideal sort is an in-place-sort whose additional space requirement is O (log$_2$ n) O (nlog$_2$ n) O (1) O (n)
An ideal sort is an in-place-sort whose additional space requirement is O (log$_2$ n) O (nlog$_2$ n) O (1) O (n)
asked
Aug 8, 2016
in
Algorithms
jothee
1.5k
views
ugcnetdec2015ii
algorithms
sorting
space-complexity
0
votes
2
answers
25
Find the Space complexity of following Code [Ace Gate Practice Booklet Vol-1 Page 127]
Find the time and Space complexity of code below : void fun(n) { if (n==1) then call A(); else { fun(n/2); fun(n/2); call B(n); } } Please note that B(n) takes O(n) time and A(n) takes O(1) time respectively. Time complexity for above code would be : $T(n) = 2T(n/2)+O(n)$ which is $O(nlog(n))$ But What will be space complexity ?
asked
Jun 2, 2016
in
Algorithms
APOORV PANSE
877
views
space-complexity
algorithms
1
vote
1
answer
26
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?
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–1, X); // Here "| ... it requires O(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
Sumit1311
594
views
space-complexity
time-complexity
geek-mock-2016
5
votes
1
answer
27
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?
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
Arjun
1.3k
views
time-complexity
space-complexity
algorithms
normal
To see more, click for the
full list of questions
or
popular tags
.
...