Questions tagged [space-analysis]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
23 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; } ...
2
votes
1answer
168 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(...
1
vote
0answers
38 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(...
1
vote
1answer
108 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: ...
2
votes
4answers
2k 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 ...
2
votes
1answer
62 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 ...
2
votes
1answer
224 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 ...
1
vote
1answer
2k 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 ...
0
votes
2answers
57 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(...
0
votes
1answer
583 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 ...
0
votes
1answer
412 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, ...
7
votes
1answer
2k 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 ...
1
vote
0answers
392 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 ...
0
votes
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 ...
2
votes
1answer
57 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 ...
0
votes
1answer
69 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-...
0
votes
1answer
367 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 ...
9
votes
2answers
9k 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 ...
6
votes
1answer
143 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 ...
0
votes
1answer
1k 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 ...
6
votes
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 ...
6
votes
1answer
34 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}\...
4
votes
1answer
419 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 ...
1
vote
2answers
2k 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 ...
3
votes
1answer
274 views

Recurrence: space complexity to Tournament Method

Tournament method have this structure to found min and max (function getMinMax): ...
0
votes
1answer
48 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 ...
6
votes
1answer
123 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 ...
3
votes
1answer
90 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 ...
1
vote
2answers
2k 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 ...
0
votes
0answers
95 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)$ ...
1
vote
2answers
4k 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|\...
3
votes
3answers
2k 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 ...
2
votes
1answer
578 views

Analysing Space Complexity

I have to compute the space complexity of this function: ...
5
votes
1answer
1k 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 ...
2
votes
4answers
611 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)...
0
votes
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? ...
1
vote
1answer
48 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\...
5
votes
1answer
8k 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 ...
1
vote
1answer
185 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 ...