Skip to main content

Questions tagged [analysis-of-algorithms]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
21 votes
3 answers

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

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

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

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

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
8 votes
2 answers

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

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

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

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

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

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

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

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

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

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,745
1 vote
2 answers

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

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

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

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

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

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

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

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

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

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