# Questions tagged [space-analysis]

The tag has no usage guidance.

44 questions
Filter by
Sorted by
Tagged with
21 views

### The total number of nodes and the height of a ternary search tree

So I need to insert into the ternary search tree (TST) about N strings. Each string is a unique ID "consists of 10 letters, the first 3 are upper case letters and the last 7 are digits" for ...
1 vote
39 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 ...
33 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 ...
1 vote
94 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 ...
849 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: ...
1 vote
62 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; } ...
719 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
51 views

539 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 ...
3k 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 ...
454 views

### Recurrence: space complexity to Tournament Method

Tournament method have this structure to found min and max (function getMinMax): ...
54 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 ...
132 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 ...
132 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
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 ...
130 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)$ ...
6k views