Stack Overflow
Stack Overflow

Questions tagged [space-complexity]

The space complexity of an algorithm quantifies the amount of memory taken by an algorithm to run as a function of the size of the input to the problem. The space complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and lower order terms.

The space complexity of a program (for a given input) is the number of elementary objects that this program needs to store during its execution. This number is computed with respect to the size n of the input data.
Formally, for an algorithm T and an input x, DSPACE(T, x) denotes the number of cells used during the (deterministic) computation T(x). We will note DSPACE(T) = O(f (n)) if DSPACE(T, x) = O(f (n)) with n = |x | (length of x).

923 questions
66
votes
3 answers

What is O(1) space complexity?

I am having a hard time understanding what is O(1) space complexity. I understand that it means that the space required by the algorithm does not grow with the input or the size of the data on which we are using the algorithm. But what does it…
coder123
  • 841
  • 1
  • 7
  • 19
64
votes
6 answers

Space complexity of recursive function

Given the function below: int f(int n) { if (n <= 1) { return 1; } return f(n - 1) + f(n - 1); } I know that the Big O time complexity is O(2^N), because each call calls the function twice. What I don't understand is why the…
George Kagan
  • 5,913
  • 8
  • 46
  • 50
56
votes
6 answers

Why does QuickSort use O(log(n)) extra space?

I have implemented the below quicksort algorithm. Online I've read that it has a space requirement of O(log(n)). Why is this the case? I'm not creating any extra data structures. Is it because my recursion will use some extra space on the stack? If…
Joey Franklin
  • 6,423
  • 7
  • 25
  • 22
48
votes
7 answers

Merge sort time and space complexity

Let's take this implementation of Merge Sort as an example void mergesort(Item a[], int l, int r) { if (r <= l) return; int m = (r+l)/2; mergesort(a, l, m); ------------(1) mergesort(a, m+1, r); ------------(2) merge(a, l, m, r); a) The time…
Frank Q.
  • 6,001
  • 11
  • 47
  • 62
40
votes
8 answers

Triplet whose sum in range (1,2)

Given n positive real numbers in an array, find whether there exists a triplet among this set such that, the sum of the triplet is in the range (1, 2). Do it in linear time and constant space. the array is not ordered. numbers are…
Trying
  • 14,004
  • 9
  • 70
  • 110
28
votes
5 answers

What is the space complexity of a recursive fibonacci algorithm?

This is the recursive implementation of the Fibonacci sequence from Cracking the Coding Interview (5th Edition) int fibonacci(int i) { if(i == 0) return 0; if(i == 1) return 1; return fibonacci(i-1) + fibonaci(i-2); } After…
committedandroider
  • 8,711
  • 14
  • 71
  • 126
27
votes
2 answers

What is the space complexity of the python sort?

What space complexity does the python sort take? I can't find any definitive documentation on this anywhere
Kamal
  • 560
  • 1
  • 5
  • 14
27
votes
7 answers

Will Arrays.sort() increase time complexity and space time complexity?

There is an array related problem, the requirement is that time complexity is O(n) and space complexity is O(1). If I use Arrays.sort(arr), and use a for loop to one pass loop, for example: public static int hello(int[]A){ Arrays.sort(A); …
aminy
  • 409
  • 1
  • 5
  • 8
26
votes
3 answers

Time/Space Complexity of Depth First Search

I've looked at various other StackOverflow answer's and they all are different to what my lecturer has written in his slides. Depth First Search has a time complexity of O(b^m), where b is the maximum branching factor of the search tree and m is…
TheRapture87
  • 1,403
  • 3
  • 21
  • 31
26
votes
10 answers

Find the k non-repeating elements in a list with "little" additional space

The original problem statement is this one: Given an array of 32bit unsigned integers in which every number appears exactly twice except three of them (which appear exactly once), find those three numbers in O(n) time using O(1) extra space. The…
Niklas B.
  • 92,950
  • 18
  • 194
  • 224
24
votes
2 answers

Memory-constrained coin changing for numbers up to one billion

I faced this problem on one training. Namely we have given N different values (N<= 100). Let's name this array A[N], for this array A we are sure that we have 1 in the array and A[i] ≤ 109. Secondly we have given number S where S ≤ 109. Now we have…
someone12321
  • 755
  • 5
  • 24
22
votes
16 answers

Given an array of integers, find the first missing positive integer in linear time and constant space

In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well. This question was asked by Stripe in it's programming interview. I have devised a solution for the same…
Jhanak Didwania
  • 581
  • 2
  • 5
  • 12
22
votes
1 answer

PHP built in functions complexity (isAnagramOfPalindrome function)

I've been googling for the past 2 hours, and I cannot find a list of php built in functions time and space complexity. I have the isAnagramOfPalindrome problem to solve with the following maximum allowed complexity: expected worst-case time…
Skatch
  • 2,112
  • 2
  • 14
  • 32
19
votes
2 answers

Why is the median-of-medians algorithm described as using O(1) auxiliary space?

Wikipedia lists the median-of-medians algorithm as requiring O(1) auxiliary space. However, in the middle of the algorithm, we make a recursive call on a subarray of size n/5 to find the median of medians. When this recursive call returns, we use…
John Kurlak
  • 6,594
  • 7
  • 43
  • 59
19
votes
1 answer

How do you find the space complexity of recursive functions such as this one?

f (int n){ if (n<=0){ return 1; } return f(n-1) + f(n-1); } Suppose we did f(4). My thought was that it would be O(2^n), since then in order to find f(n-1) + f(n-1) we would have to push f(n-1) = f(3) to the call stack twice,…
kubernetes
  • 213
  • 2
  • 5
1
2 3
…
61 62