# Questions tagged [analysis-of-algorithms]

The tag has no usage guidance.

25 questions
Filter by
Sorted by
Tagged with
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 ...
• 284
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 ...
• 4,020
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 - ...
• 341
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, ...
• 311
542 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 ...
• 307
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 ...
• 183
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 ...
• 171
462 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 ...
• 369
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 ...
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 ...
• 303
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 ...
• 145
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 ...
• 121
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 ...
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 ...
• 137
527 views

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,745 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 ... • 91 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}... • 111 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 ... • 225 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 \... • 11 0 votes 1 answer 524 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 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 ... • 111 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$ ...
• 21
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 = \...