# Questions tagged [space-analysis]

The tag has no usage guidance.

43 questions
Filter by
Sorted by
Tagged with
1answer
5k 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 ...
2answers
13k 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 ...
2answers
1k 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 ...
1answer
12k 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 ...
1answer
37 views

0answers
511 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 ...
1answer
72 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-...
2answers
70 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(...
1answer
581 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 ...
1answer
2k 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 ...
1answer
50 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 ...
0answers
7 views

### How can we transform elements of FMEA into spaces and transitions in Colored Petri net?

To ensure safety for systems, hazard analysis can be performed. FMEA is one of an effective technique to analyze systems. FMEA analyze systems potential hazards. To see the behavior of system, colored ...
1answer
877 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 ...
1answer
542 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, ...
0answers
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 ...
0answers
122 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)$ ...
0answers
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? ...
1answer
133 views

...