Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [algorithm-analysis]

Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage. Use the [runtime-analysis] tag for questions about the runtime of algorithms.

2,019 questions
Filter by
Sorted by
Tagged with
15 views

### How to count primitive Operations

ive been struggling with counting primitive operations. I know that you do not have to outline every operation that happens in your pseudocode but this is never the less a bit complicated for me. ...
18 views

### Time complexity of optimal index

Consider a data structure that stores a set of $n$ objects, where each object is a map of arbitrary key-value pair. The data structure maintains a reverse lookup table, where for each key-value pair, ...
• 133
1 vote
38 views

### Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion

We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, ...
• 111
32 views

### Algorithmically determine if another algorithm is brute force?

Is there a way to algorithmically determine if another algorithm is a brute force algorithm? Can a Turing machine be programmed to do this? related: "Precise definition of a brute force algorithm&...
• 152
28 views

### Why is it impossible to do a linear time radix sort on n integers and ranging from $0$ to $n^{3} - 1$?

I propose by doing a base-n expansion of the numbers, we have that since there are $n^{3}$ values and $n$ digits in this expansion, there are a total of $\log_{n} n^{3} = 3$ digits. Note in this base-...
• 103
26 views

• 81
18 views

### Analysis of Simon's Algorithm: Probability Expression for Matching Queries

The Simon's problem is that, given a function $f:\{0,1\}^n\to\{0,1\}^n$ such that, for all $x,y\{0,1\}^n$ t satisfies $$f(x)=f(y)\text{ iff }x=y\oplus s$$ where $s\in \{0,1\}^n$, and the Simon's ...
• 139
585 views

### Possible Mistake in Skiena's Algorithm Design Manual

In Skiena's book Algorithm Design Manual, 3rd Edition, it is claimed on page 45 that $$mn - m^2 + m \in \Omega(mn)$$ where $m,n \geq 0$ and $m \leq n$. I claim that this is in fact false, with the ...
• 173
122 views

### Find the longest northeast path in $O(n\log n)$ time

Given a set $Z$ of $n$ points $(p_1,p_2,p_3, \ldots,p_n)$. The coordinates of these points are arbitrary numbers and are unsorted. If they give me $s$ and $t$ to be two points in $Z$. A northeast path ...
• 121
1 vote
96 views

### Quick sort with $K-1$ pivots

I was thinking about quicksort with multiple pivots and I came across this question. How can we efficiently implement a version of Quicksort where we choose $k−1$ pivots to partition an array of ...
1 vote
63 views

### Find all the induced paths with a start vertex

Let $G$ be a graph and let $v$ be a vertex. Is there a polynomial algorithm for the following operation? Operation. Find all the induced paths in $G$ with first vertex $v$. Background This problem is ...
• 405
87 views

### Amortized cost for Stack Operations

In this problem we consider two stacks $A$ and $B$ manipulated using the following operations ($n$ denotes the size of $A$ and $m$ the size of $B$):   PushA($x$): Push element $x$ on stack $A$.   ...
• 1
24 views

### Is bitonic sort order preserving on keys with the same value?

We are all familiar with Bitonic Sort. The computations are predetermined and data-independent. Let's say we have a table A = [ 1,3,2,5,6,3,3,21 ]. The output ...
• 23
267 views

### Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"

I was referring to the textbook Artificial Intelligence: A modern approach 3rd by Stuart Russell and Peter Norvig. what to prove about the general "graph search": (Here I assume "within ...
• 203
1 vote
65 views

### Scheduling classes with lower and upper bounds on students and classes

I am struggling to solve the following excercise: Design an assignment of a group of n students to m classes. Student i should take a minimum of $l_i$, and a maximum of $u_i$ within a set C1 of ...
1 vote
83 views

### Amortised cost - transferring tokens

I'm trying to solve a problem from one of the older exams. Question: There's an infinite, one-dimensional board, with fields numbered consecutively $\ldots, -2, -1, 0, 1, 2, \ldots$ A move in the ...
• 113
1 vote
180 views

### Number of stops during trip - Dynamic programming algorithm

I am attending a course about algorithm design, and I have found an old test which has once been submitted. However, I don't have the solutions to it, and I am having some trouble with one specific ...
392 views

### Prove that the number of comparisons between elements in binary heap build is at most (2n-2)

Question Prove that the number of comparisons between elements in binary heap build is at most $2n-2$. $n$ is the total number of the nodes. Pseudocode ...
• 143
38 views

### Does the Master Theorem apply to T(n) = 3T(n/3) + n/log2(n)?

Id say this is the first case of Master Theorem, but when I try to prove that the limit of f(n)/ n ^ (1-E) is 0, I cannot do it. Does anyone have a solution?
777 views

### What is the name of this search algorithm?

I was thinking about an efficient binary search for unsorted arrays with $n$ entirely unique elements, and came up with something that probably already exists. Here's how it works: At each level of ...
92 views

### Proof about Existence of Stable Matching

I've read the stable matching chapter in Kleinberg and Tardos's Algorithm Design and was wondering how one can show whether a stable matching under a given set of constraints exists. K&T introduce ...
1 vote
90 views

### Running time of modified BFS algorithm to find shortest path in weighted DAG

While the shortest path can be calculated with $O(V+E)$ time over a weighted directed acyclic graph using topological sort, I wonder about the running time of the following BFS type algorithm I ...
• 113
33 views

### Expected number of mistakes grows logarithmically in number of iterations - improving performance?

I am reading a paper (link) in which an algorithm proposes a solution $\hat{\mathbf x}^{(t)}$ in each iteration $t = 1, \dots, T$, and each time, learns the true solution $\mathbf x^{(t)}$, so we ...
• 21
46 views

...
• 263
1 vote
11 views

18 views

### Semantically Compare Programs by Similarity?

In NLP, it's common to study the semantic similarity between pieces of text, which can be calculated in a number of ways. Are there any tools, methods, algorithms or processes that can be used to ...
53 views

### Optimal algorithm to select unique values from a daily-growing list

Suppose I have a list of numbers, say $L$, that grows every day when a new batch of numbers get added to it every night. Right now, say the list is of size $M$, with the daily batch size is of the ...
• 101
59 views

### Question about implication in proof that predecessor subgraph is a breadth-first tree

Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS: Theorem 22.5: (Correctness of breadth-first search) Let $G = (V, E)$ be a directed or undirected graph, ...
1 vote
252 views

### Question about step in proof that predecessor subgraph forms a breadth-first tree

Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS: Theorem 22.5: (Correctness of breadth-first search) Let $G = (V, E)$ be a directed or undirected graph, ...
184 views

### What is the time complexity of this algorithm of finding all prime numbers?

I came up with this algorithm for finding all prime numbers from 1 to n. This algorithm could already exist, if it does I don't know what it is called. ...
1 vote
41 views

### Finding growth rate of T(n) of a code segment

I am presented with the following code segment and asked to find the growth rate, which can be done by finding the number of times the variable sum is incremented: ...
79 views

### Is a predecessor subgraph always connected?

Given an undirected graph $G$ with non-negative edge weights, how can we prove that the predecessor subgraph $G_{p}$ of $G$ is always connected? Here's how the predecessor subgraph is defined: for a ...
1 vote
24 views

### Why must a safe configuration be reached in n^2 + n rounds in Dijkstra's Self-stabilizing mutual exclusion algorithm?

In the book Self-Stabilization (Dolev, 2000) the author provides a proof (p.19) of Dijkstra's self-stabilizing mutual exclusion algorithm. An excerpt of the book showing the proof is found below. At ...
• 11