Recent questions tagged space-complexity

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 in Algorithms by sripo Junior (755 points) | 37 views

+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 in Algorithms by Shivani gaikawad Junior (717 points) | 66 views

0 votes

0 answers

3

Space Complexity of Dijkastra's algorithm

asked Jul 5 in Algorithms by Hardik Maheshwari (81 points) | 155 views

0 votes

0 answers

4

#Algorithms Space Complexity Vs Auxiliary Space Complexity?

asked Jun 26 in Algorithms by iarnav Loyal (9k points) | 38 views

0 votes

0 answers

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 in Algorithms by Hardik Maheshwari (81 points) | 93 views

0 votes

1 answer

6

Evaluation of Postfix expression using stack

asked May 6 in DS by JaiKumar Guwalani (11 points) | 294 views

0 votes

1 answer

7

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

asked Apr 26 in Algorithms by Akash Kumar Roy (493 points) | 198 views

0 votes

2 answers

8

MY DOUBT: Worst case space complexity of Quick sort (NOT FOR A STRAIGHT ANSWER)

asked Apr 21 in DS by Akash Kumar Roy (493 points) | 137 views

+1 vote

0 answers

9

How large can the ratio of two memory requirements get?

asked Mar 3 in DS by XbrucewayneX (111 points) | 93 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.

asked Jan 12 in Programming by Asim Abbas (225 points) | 97 views

+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 (101k points) | 96 views

+2 votes

1 answer

12

How to determine the time complexity of this loop?

asked Nov 7, 2017 in Algorithms by Narasimhan (125 points) | 234 views

+5 votes

1 answer

13

In-place Merge Sort via Doubly linked list in place of Array

asked Nov 2, 2017 in Algorithms by Chhotu Boss (11.4k points) | 207 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

asked Feb 8, 2017 in DS by smartmeet Active (5k points) | 194 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

asked Feb 7, 2017 in Algorithms by smartmeet Active (5k points) | 167 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

asked Feb 5, 2017 in Programming by reena_kandari Loyal (8k points) | 257 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)); }

asked Jan 28, 2017 in Algorithms by sripo Junior (755 points) | 107 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?

asked Dec 8, 2016 in Algorithms by rahul sharma 5 Boss (25.4k points) | 234 views

+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) | 906 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

asked Nov 3, 2016 in Algorithms by parthbkgadoya (367 points) | 349 views

+4 votes

1 answer

21

Space Complexity of sorting

asked Oct 19, 2016 in Algorithms by KISHALAY DAS Loyal (6.6k points) | 434 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.

asked Oct 12, 2016 in Algorithms by Shyam Singh 1 Active (1.5k points) | 224 views

0 votes

2 answers

23

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

asked Jun 2, 2016 in Algorithms by APOORV PANSE (173 points) | 581 views

+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) | 346 views

+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 (363k points) | 538 views

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 questions tagged space-complexity

Recent Posts

Recent Blog Comments