Questions tagged [analysis-of-algorithms]
The analysis-of-algorithms tag has no usage guidance.
25
questions
21
votes
3
answers
1k
views
Using Kolmogorov complexity as input "size"
Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$.
Normally in the analysis of algorithms or computational complexity theory, we have some ...
18
votes
1
answer
2k
views
Polynomial speedups with algorithms based on semidefinite programming
This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time.
I am still puzzling over the actual running time of algorithms that compute the solution of ...
17
votes
6
answers
777
views
When have we found better bounds for known algorithms?
Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - ...
10
votes
2
answers
3k
views
Random walk and mean hitting time in a simple undirected graph
Let $G=(V,E)$ be a simple undirected graph on $n$ vertices and $m$ edges.
I'm trying to determine the expected running time of Wilson's algorithm for generating a random spanning tree of $G$. There, ...
9
votes
1
answer
512
views
Most efficient inplace merge algorithms (stable and unstable)
I am currently researching the best algorithms available to achieve an inplace merge operation: consider two consecutive sorted arrays of size n and ...
7
votes
2
answers
358
views
Given a subset of the hypercube and a copy translated by s, find s
Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible ...
6
votes
1
answer
150
views
What is the state of the art research in analysing algorithms on GPU architectures?
I have found many papers on sequential algorithms that have been implemented and tested on GPU architectures. Each of these papers usually as a result contains the amount of speedup that was achieved ...
5
votes
2
answers
330
views
What is the relevance of Real Analysis in TCS?
I'm a recent Math major who switched to a double major with Computer Science.
I'm petitioning my CS Department Chair to allow me to take Real Analysis in place of Algorithms. I've already taken Data ...
3
votes
1
answer
166
views
Proof techniques for string algorithms?
I'm currently reading through the tome "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield, and I find the proofs to be extremely case analysis heavy and full of finicky +-1s. This seems ...
3
votes
0
answers
77
views
Monotonic and bounded sequences throughout computer science
When I refer to the Monotone Convergence Theorem below, I refer to the very simple claim that if a non-decreasing sequence has an upper bound then it converges. I don't refer to the claim from Measure ...
2
votes
1
answer
749
views
What are good conferences for algorithms about finite automata?
I am writing a research paper, which describes some properties about finite automata. It also provides a couple of algorithms that can measure some aspects of the properties.
Could you point out some ...
2
votes
2
answers
341
views
How to treat dynamic memory allocation in algorithm analysis?
I have an algorithm in which I want to dynamically allocate some memory.
Let's say that I have N numbers and that I want to describe some binary relation over them. To do so I want to create a N*N ...
2
votes
0
answers
87
views
Dynamic connectivity with known history, for maximal connected component span
Consider a graph in which edges are added and removed over time. Define the span of a connected component as the product of its number of vertices and the longest duration for which it remains a ...
2
votes
0
answers
87
views
Is there any research on the complexity of producing given a problem description?
It is straightforward enough to analyze the complexity of a particular algorithm as a function of input size or other variables in terms of runtime or space used or whatever else. I am wondering if ...
2
votes
0
answers
527
views
Tricky big-O calculation
I have a recursive algorithm in which the time for each step depends on the time for smaller steps. Essentially a structure is built at steps 1, 2, ..., n which must be searched at larger heights:
$$
...
1
vote
2
answers
307
views
Complexity analysis on a parameterized recurrence relation
In order to analyse the complexity of our algorithm, we try to solve this recurrence:
$T(n)=3T(n-1)-T(n-2)+T(n-k)+3^k$ ; in which $k$ is a parameter to be fixed.
We know that this kind of ...
1
vote
0
answers
58
views
Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them
In integer multiplication algorithms such as the Schonhage-Strassen algorithm (and the recently described Harvey and van der Hoeven algorithm), integers of size $n$ are reduced to polynomials with ...
1
vote
1
answer
105
views
Which is the most efficient of the two following approximation algorithms?
Let $\mathfrak{B}$ be a set, which will be called the set of bins. Suppose we have five maps
\begin{align*}
\mathrm{Value} &: \mathfrak{B} \to \mathbb{R}
\\
\mathrm{Upper} &: \mathfrak{B}...
1
vote
0
answers
412
views
Computational complexity of polynomial interpolation with k non-zero terms
I am attempting to find a complexity for computing the order polynomial of partially ordered sets on a special family, and have come across the following problem. Assume we have the following values ...
1
vote
0
answers
45
views
Bounding the cost of an approximation algorithm when subtraction involve [closed]
Given an algorithm with approximation ratio $\alpha$, and another algorithm with approximation ratio $\beta=n^\epsilon$, and a solution to a problem with cost $c$. What is the standard way to bound $\...
0
votes
1
answer
502
views
What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?
Let $X$ be the universe of elements, $F$ a collection of subsets $S \subseteq X$, each with an associated cost. The goal is to find a subcollection $C \subseteq F$ of minimum total cost which covers $...
0
votes
0
answers
74
views
Complexity of an algorithm involving permutations
I'm looking to figure out the computational complexity of an algorithm in an application I've written. The application computes the answer to a problem that is $\#P$-hard, and the algorithm I'm asking ...
0
votes
0
answers
69
views
Frogs Game Amortized Analysis
The game is defined by two integer parameters: n and k.
We are given an array of n sets:
$$S_1, S_2, ...., S_n$$
such that, each of them is a subset of
$\{1, 2, ..., k\}$.
Adversary picks a set $S_i$ ...
-1
votes
1
answer
86
views
How is additive error handled in this simple algorithm? 'Product of all elements'
Say we have two unit vectors $\hat{u}, \hat{v} \in \mathbb{R}^n$ where $\hat{u} = (u_1,...,u_n)$ and $\hat{v}$ approximates $\hat{u}$. $~\hat{v} = (u_1+\epsilon, ...,u_n+\epsilon)$ where $\epsilon = \...
-7
votes
1
answer
4k
views
Travelling sales man with Quantum Computers [closed]
I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for ...