Skip to main content

Questions tagged [analysis-of-algorithms]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
2 answers
458 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 ...
0 votes
0 answers
77 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 ...
9 votes
1 answer
540 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 ...
1 vote
0 answers
59 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
106 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}...
0 votes
0 answers
72 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$ ...
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 ...
0 votes
1 answer
522 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 $...
3 votes
0 answers
78 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 ...
3 votes
1 answer
168 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 ...
17 votes
6 answers
782 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 - ...
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 ...
8 votes
2 answers
360 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 ...
-1 votes
1 answer
90 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 = \...
1 vote
0 answers
413 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 ...
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, ...
1 vote
2 answers
312 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 ...
2 votes
2 answers
344 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 ...
-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 ...
6 votes
1 answer
151 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 ...
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 $\...
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 ...
2 votes
1 answer
777 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 ...
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 ...
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: $$ ...