Questions tagged [space-analysis]

The tag has no usage guidance.

43 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
37 views

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 ...
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-...
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(...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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)$ ...