# Questions tagged [analysis-of-algorithms]

The tag has no usage guidance.

17 questions
Filter by
Sorted by
Tagged with
37 views

### Binary Search Algorithm [closed]

The problem is from Data Structures and Algorithm Analysis Edition 3.2 (Java Version) Book from Clifford A. Shaffer. It is from the third chapter exercises, problem number 3.13.20. Below is how it is ...
643 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 - ...
79 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 ...
324 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 ...
54 views

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 ...
516 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 ...
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:  ...