# Recent questions tagged space-complexity 1 vote
0 answers
1
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.
5 votes
2 answers
2
What is the space complexity of the following code? $O(logn)$ $O(n)$ $O(nlogn)$ $O(1)$
1 vote
1 answer
3
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????
0 votes
0 answers
4
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!
0 votes
1 answer
5
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 ?
1 vote
1 answer
6
What is time and space complexity to evaluate postfix expression ?
1 vote
2 answers
7
what is Space complexity of Huffman coding?
0 votes
3 answers
8
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?
1 vote
0 answers
9
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.
3 votes
1 answer
10
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.
3 votes
2 answers
11
Worst case and best case space complexity of merge sort is ___________________________
2 votes
1 answer
12
// 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/
5 votes
1 answer
13
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.
2 votes
1 answer
14
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
0 votes
0 answers
15
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
0 votes
1 answer
16
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
3 votes
1 answer
17
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)); }
0 votes
0 answers
18
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?
8 votes
2 answers
19
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...
6 votes
2 answers
20
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
4 votes
1 answer
21
0 votes
1 answer
22
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.
0 votes
1 answer
23
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
2 votes
3 answers
24
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)
0 votes
2 answers
25
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 ?
1 vote
1 answer
26
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&ndash;1]*arr[n&ndash;1] > X) return fun(arr, n&ndash;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 &ndash; A How to calculate space complexity?
42 votes
4 answers
27
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$
5 votes
1 answer
28
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?
To see more, click for the full list of questions or popular tags.