Skip to main content

Questions tagged [space-analysis]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11 votes
5 answers
3k views

Does an algorithm's space complexity include input?

Consider the Kadane's algorithm for finding maximum subarray within an array: ...
Eugene Yarmash's user avatar
2 votes
0 answers
397 views

Data Structure for finding all bounding boxes that overlap or are contained in a given bounding box

I am looking for a data structure that needs to have very fast and accurate queries to solve the following: The input: A set of 3 Dimensional axis-aligned bounding boxes B A separate 3D axis aligned ...
yo76yo's user avatar
  • 21
0 votes
1 answer
79 views

can similarity transformation be linear transformation?

Learning Computer Graphics - Can similarity transformation be linear transformation? Similarity T is a rigid transformation (translation and rotations) with uniform scaling. so I guess a similarity ...
learningtocode's user avatar
1 vote
1 answer
477 views

Index variable takes up log(n) space?

In the definition of in-place algorithm, from Wiki, " However, this form is very limited as simply having an index to a length n array requires O(log n) bits." How does an array index ...
wangge's user avatar
  • 113
2 votes
1 answer
2k views

what will be space complexity for snippet for(i=1 to n) int x=10;?

The space complexity of the code snippet given below: ...
ashish's user avatar
  • 33
1 vote
1 answer
95 views

The space complexity of a function that allocates space based on the input value and not size

What is the space complexity of the following hyphotetical function: void function(int n) { int[] array = new int[n]; // allocate array of size n return; } ...
lolski's user avatar
  • 115
3 votes
1 answer
827 views

Worst Case Space Complexity of Merge Sort and Bubble Sort

I understand that the worst space complexity of Bubble Sort is constant O(1), since all the space we need is the array where the elements were stored. But why is Merge Sort's worst space complexity O(...
alyssaeliyah's user avatar
1 vote
0 answers
66 views

Is there a difference in space complexity between inner product of matrices to multiple of inner products where each containing one matrix at a time?

The book I am reading is suggesting the following: Suppose I have two vectors $v, w$ and $P(n)$ matrices $U_1, U_2, \ldots, U_{P(n)}$. Then performing an inner product of $v$ with $U_1U_2\ldots U_{P(...
bilanush's user avatar
  • 263
1 vote
1 answer
317 views

Big O space complexity of this isAnagram method

I'm currently debating with some friends what is the Big O space complexity of this isAnagram method: ...
user avatar
3 votes
4 answers
5k views

Chess Knight minimum moves to destination on an infinite board

There are tones of solutions for Knights tour or shortest path for Knights movement from source cell to destination cell. most of the solutions are using BFS which seems the best algorithm. Here is ...
Amir-Mousavi's user avatar
2 votes
1 answer
70 views

Is there a measure of space usage over time?

We typically measure algorithm efficiency by space efficiency and then time efficiency e.g. this algorithm takes O(n) time and O(n) space. However, I feel this does not capture the full story. Say we ...
Daniel's user avatar
  • 189
3 votes
1 answer
524 views

A* 8-puzzle problem worst case memory usage

We are testing the A* algorithm with Hamming and Manhattan on the 8-puzzle (and its natural generalization n-puzzle) problem. We have to answer the following question but I can't figure out what it ...
Principis's user avatar
2 votes
1 answer
6k views

Python: A doubt on time and space complexity on string slicing

This qns is from my school's exam paper. Context: In a game of Hangman, player tries to uncover a hidden word by guessing the letters in the word. Assume all words and letters are lowercase. The ...
Prashin Jeevaganth's user avatar
1 vote
2 answers
169 views

Space efficient data structure for subsets of [1:n]

Let $S= \{1,2,3...,n\}$ be a set and I want to store a subset of $A \subseteq S$. Is there exists any data structure such that insert$(x)$, delete ($x$) can be done in amortised $O(1)$ time and search(...
Complexity's user avatar
  • 1,187
0 votes
1 answer
1k views

Iterative DFS space complexity O(|E|)? Same vertex appears multiple times in stack?

I'm referring to a question already asked on stackoverflow: https://stackoverflow.com/questions/25988965/does-depth-first-search-create-redundancy However I'm not quite convinced by the answers ...
Stefan J.'s user avatar
0 votes
1 answer
750 views

What is the time and space complexity of Rete algorithm

I am working on pattern matching algorithm. Its working and using very less memory. For the comparison, I have to compare it with the Rete Algorithm. I have checked it in the thesis of the author, ...
Shahensha Khan's user avatar
31 votes
1 answer
11k views

Does space complexity analysis usually include output space?

Since most examples of complexity analysis I've seen involve functions that return either nothing (e.g. in-place sort) or a single value (e.g. computation, lookup), I haven't been able to figure this ...
Kevin Kibler's user avatar
1 vote
0 answers
623 views

How to calculate multibit trie storage size?

I wish to use a multi-bit trie structure for storing IPv4 forwarding information with a fixed stride width of 8 bits, I think this is also called a "radix of 8" (so for any IP prefix 4 levels will ...
Baldrick's user avatar
  • 111
0 votes
0 answers
27 views

Space complexity and recurrence equation of a recursive method [duplicate]

I recently had to do the assignment to determine the space complexity of methods similar to the following. I need to state the recurrence equation (line by line), derive the closed form and use that ...
Tim Bruyn's user avatar
2 votes
1 answer
85 views

What is the complexity to show this theorem?

Given a sum of regular expressions, where each regular expression in the sum is n-1 concatenations of 0, 1 and (0+1). There is need to show that the sum of all regular expressions is either equal to ...
Farewell Stack Exchange's user avatar
0 votes
1 answer
76 views

How large would a database containing perfect knowledge of chess be?

Assuming that a database entry schema contains two 64-bit hash IDs generated via the algorithm explained here, in the section "Generating Hash Keys for Chess Boards", and simply a score that's a 32-...
Patrick Roberts's user avatar
0 votes
1 answer
890 views

Does array always have a wasted space of O(n)?

In this question it's stated that dynamic array wasted space is O(n). Here is the explanation why: Because, when a dynamic array is full, its size is increased by some factor ...
Max Koretskyi's user avatar
12 votes
3 answers
17k views

Why is DFS considered to have $O(bm)$ space complexity?

According to these notes, DFS is considered to have $O(bm)$ space complexity, where $b$ is the branching factor of the tree and $m$ is the maximum length of any path in the state space. The same is ...
user avatar
6 votes
1 answer
223 views

Memory needed for computational graph

Suppose we have a set of equations like this p7=f(p1+p6); p6=f(p2+p5); p5=f(p3+p4); p4=f(p3); p3=f(p2); p2=f(p1); p1=f() It can be represented by computational ...
Yaroslav Bulatov's user avatar
0 votes
1 answer
3k views

Why do depth-limited search algorithm and BFS have different memory complexity?

Let be $b$ the branching factor of the tree. Let be $d$ the depth of the shallowest solution. Let be $l$ the limit given to depth-limited search algorithm Why is depth-limited search algorithm ...
Revolucion for Monica's user avatar
7 votes
2 answers
2k views

Space complexity of string indices: O(1) or O(log|S|)?

Say you have a string S and wish to store indices of it, e.g. letter at index 3 of "toast" is 'a'. Seems that people generally consider an index as taking ...
sudo's user avatar
  • 173
6 votes
1 answer
47 views

Showing strong connectivity is in DSPACE((logn)^2)

$ST-CONN = \text{{(G,s,t) | G is directed graph, there's path from s to t}}$ I've learned the following deterministic algorithm to solve the problem in $log^2n$ space: $\psi(G,s,t,k) :$ $\hspace{1cm}\...
sel's user avatar
  • 385
4 votes
1 answer
586 views

Is FKS hashing really linear space?

In FKS hashing, I wonder if the size of the table $G[ 1..n]$ (used to record the functions $g_i$ which is chosen randomly; one entry per bucket) is really strictly $O(n)$. Given that the probability ...
Thomas Mueller's user avatar
2 votes
2 answers
4k views

With Memoization Are Time Complexity & Space Complexity Always the Same?

I am studying Dynamic Programming using both iterative and recursive functions. With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of ...
Fairly Nerdy's user avatar
3 votes
1 answer
520 views

Recurrence: space complexity to Tournament Method

Tournament method have this structure to found min and max (function getMinMax): ...
eightShirt's user avatar
0 votes
1 answer
57 views

Searching through all program of a stack-based language with little memory

I wrote a simple stack based language, and am looking to exhaustively generate all programs for it, to find the shortest program that generates a particular output. Given a program fragment, I can ...
SRobertJames's user avatar
6 votes
1 answer
135 views

How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?

Let $\mathbf{X}$ be a $n \times n$ matrix. Given that we can only keep $k$ rows ($k << n$) or columns of the matrix in memory, how can we compute $\mathbf{X}^T \mathbf{X}$ while minimizing the ...
erensezener's user avatar
3 votes
1 answer
148 views

Is the memory usage of total languages deterministic?

I'm interested in the memory usage of various programming languages when implemented on actual hardware. I believe that a Turing-complete programming language has, in general, unknowable memory usage ...
oconnor0's user avatar
  • 393
1 vote
2 answers
3k views

How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path?

The Naive way to reduce space complexity of Floyd-Warshall algorithm is consider only $d_{ij}^{(k)}$ and $d_{ij}^{(k-1)}$ in each time. But in this case, we can't track actual shortest path with ...
Maddy's user avatar
  • 153
0 votes
0 answers
137 views

Time complexity in relation to data size

Not sure if I completely understand this problem that was presented in class. We were given function $$f(n) = 2*f(n-1) + n$$ The base case for all these functions $f(1)$ is equal to 1. Assume $T(x)$ ...
Jakub Kawalec's user avatar
4 votes
2 answers
6k views

Space complexity of directed and undirected graph

I have started reading graph theory from Introduction to Algorithm. The author starts by saying that if the graph is dense then: $$|E|\text{ close to }|V|^2$$ else if the graph is sparse then: $$|E|\...
CodeYogi's user avatar
  • 281
5 votes
3 answers
5k views

Memory usage of a BST or hash table?

I would like to use a data structure allowing fast access, either a balanced binary search tree (BST) for $O(\log n)$ access time or an open hash table for constant access time. 1) What is the exact ...
user7060's user avatar
  • 465
2 votes
1 answer
814 views

Analysing Space Complexity

I have to compute the space complexity of this function: ...
Sagnik's user avatar
  • 894
5 votes
1 answer
2k views

Since we need space for recursive calls, is the space complexity of the recursive factorial is n?

As Wikipedia says, quickSort needs O(log n) extra space when the following conditions are met: In-place partitioning is used. This unstable partition requires O(1) space. After partitioning, the ...
Maksim Dmitriev's user avatar
2 votes
4 answers
3k views

What is more important in an algorithm, small runtime or small memory usage?

I have two client-server protocols which perform the same function but they have different complexities in time (in terms of number of operations) and space (in terms of number of objects of same type)...
user7060's user avatar
  • 465
0 votes
0 answers
22 views

Runtime and space usage of a snippet of code [duplicate]

I've been trying to understand time complexity and space complexity by writing my own snippets of code and solving them. Can you see if I'm correct? ...
nightmarish's user avatar
1 vote
1 answer
51 views

Is it possble to store a counter that could reach $\lfloor \frac{N}{x}\rfloor$ using $\lceil\log_2(N+1)\rceil$ - $\lfloor\log_2 x\rfloor$ bits?

Let $x,N$ be positive integers. I'd like to store a counter which could reach value of $\left\lfloor \frac{N}{x}\right\rfloor$ (i.e. could take any value in $0,1,\ldots,\frac{N}{x}$) using $$\lceil\...
A C's user avatar
  • 11
7 votes
1 answer
17k views

Can anybody explain intuitively why quick sort need log(n) extra space and mergesort need n?

I've searched on internet and everybody said it's stack space needed on recursion. I know log(n) extra space for quick sort happened when use in place, but still I don't get it. Anybody can explain ...
Guest's user avatar
  • 79
1 vote
1 answer
289 views

Time/Space cost of Taxicab algorithm?

The following is an algorithm for generating "Taxicab numbers" using a priority queue (pq). Vector is an arbitrary data type ...
Jenna Maiz's user avatar