Recent questions tagged space-complexity

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.

sripo asked in Algorithms Nov 6, 2018

by sripo

1.1k views

5 votes

2 answers

2

Test Algorithms
What is the space complexity of the following code? $O(logn)$ $O(n)$ $O(nlogn)$ $O(1)$

Shivani gaikawad asked in Algorithms Aug 17, 2018

by Shivani gaikawad

508 views

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 ????

Hardik Maheshwari asked in Algorithms Jul 5, 2018

by Hardik Maheshwari

2.2k views

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!

iarnav asked in Algorithms Jun 26, 2018

by iarnav

320 views

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 ?

Hardik Maheshwari asked in Algorithms Jun 14, 2018

by Hardik Maheshwari

2.2k views

1 vote

1 answer

6

Evaluation of Postfix expression using stack
What is time and space complexity to evaluate postfix expression ?

JaiKumar Guwalani asked in DS May 6, 2018

by JaiKumar Guwalani

1.5k views

1 vote

2 answers

7

Space complexity of Huffman coding
what is Space complexity of Huffman coding?

Akash Kumar Roy asked in Algorithms Apr 26, 2018

by Akash Kumar Roy

1.9k views

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?

Akash Kumar Roy asked in DS Apr 21, 2018

by Akash Kumar Roy

1.6k views

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.

XbrucewayneX asked in DS Mar 3, 2018

by XbrucewayneX

220 views

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.

Asim Abbas asked in Programming Jan 12, 2018

419 views

3 votes

2 answers

11

Space complexity
Worst case and best case space complexity of merge sort is ___________________________

srestha asked in Algorithms Nov 11, 2017

295 views

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/

Narasimhan asked in Algorithms Nov 7, 2017

742 views

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.

Chhotu asked in Algorithms Nov 2, 2017

by Chhotu

892 views

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

smartmeet asked in DS Feb 8, 2017

324 views

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

smartmeet asked in Algorithms Feb 7, 2017

262 views

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

reena_kandari asked in Programming Feb 5, 2017

by reena_kandari

525 views

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)); }

sripo asked in Algorithms Jan 28, 2017

by sripo

201 views

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?

rahul sharma 5 asked in Algorithms Dec 8, 2016

by rahul sharma 5

542 views

9 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...

vineet.ildm asked in Algorithms Nov 7, 2016

3.5k views

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

parthbkgadoya asked in Algorithms Nov 3, 2016

by parthbkgadoya

554 views

4 votes

1 answer

21

Space Complexity of sorting

KISHALAY DAS asked in Algorithms Oct 19, 2016

by KISHALAY DAS

690 views

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.

Shyam Singh 1 asked in Algorithms Oct 12, 2016

by Shyam Singh 1

519 views

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

parulnabi asked in Algorithms Sep 2, 2016

317 views

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)

jothee asked in Algorithms Aug 8, 2016

by jothee

1.6k views

0 votes

2 answers

25

Find the Space complexity of following Code [Ace Gate Practice Booklet Vol-1 Page 127]

APOORV PANSE asked in Algorithms Jun 2, 2016

by APOORV PANSE

1.3k views

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?

Sumit1311 asked in Algorithms Jan 26, 2016

711 views

46 votes

4 answers

27

GATE CSE 2005 | Question: 81a
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 space complexity of the above code is? $O(1)$ $O(n)$ $O(n!)$ $n^n$

Kathleen asked in Algorithms Sep 22, 2014

13.4k views

5 votes

1 answer

28

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?

Arjun asked in Algorithms Aug 29, 2014

by Arjun

1.6k views

To see more, click for the full list of questions or popular tags.

Follow @gateoverflow

GATE Overflow

Recent questions tagged space-complexity

Search GATE Overflow