Questions tagged [analysis-of-algorithms]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Andrew's user avatar
  • 284
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 ...
Alessandro Cosentino's user avatar
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 - ...
Rob Simmons's user avatar
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, ...
arekolek's user avatar
  • 311
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 ...
Vincent's user avatar
  • 307
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 ...
boinkboink's user avatar
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 ...
ksm001's user avatar
  • 171
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 ...
wonderinghuh's user avatar
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 ...
Siddharth Bhat's user avatar
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 ...
wlad's user avatar
  • 303
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 ...
JackWM's user avatar
  • 145
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 ...
user931392's user avatar
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 ...
Matthieu Latapy's user avatar
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 ...
Joel Croteau's user avatar
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: $$ ...
Charles's user avatar
  • 1,735
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 ...
Leo's user avatar
  • 91
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 ...
Vighnesh Iyer's user avatar
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}...
Bob's user avatar
  • 111
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 ...
Max Hopkins's user avatar
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 $\...
liron's user avatar
  • 11
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 $...
Frizzylicious's user avatar
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 ...
Matt Samuel's user avatar
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$ ...
R.hatam's user avatar
  • 21
-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 = \...
stats_man97531's user avatar
-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 ...
alkabary's user avatar