# Tag Info

## Hot answers tagged algorithm-analysis

Accepted

### Measuring time complexity in the length of the input v/s in the magnitude of the input

You're not missing anything -- you are correct! Consider a loop that prints Hello World $n$ times, where $n$ is an integer, then by the same procedure as above, this algorithm would also be ...
• 6,958

### Measuring time complexity in the length of the input v/s in the magnitude of the input

@CalebStanford's answer is excellent, but just to add one point: There is a distinction between how many operations are needed and how many bits are needed (more for each number of many digits), and ...
• 227
Accepted

### Why don't integer multiplication algorithms use lookup tables?

Some integer multiplication algorithms do use lookup tables. The IBM 1620 Model I "CADET" lacked a conventional ALU: addition and subtraction used a 100 digit table; multiplication used a ...
• 886

### How to prove greedy algorithm is correct

Jeff Ericson in his "Algorithms" states three conditions: Greedy choice: There is an optimal solution that includes the choice the algorithm makes. Inductive structure: The smaller ...
• 13.9k

### What is the time complexity of this algorithm of finding all prime numbers?

The following complexity is not tight; however closeby: The complexity of the algorithm is at least $\Omega(n \sqrt{n}/\log^2 n)$ and at most $O(n \sqrt{n}/\log n)$. For any natural number $x$, the ...
• 5,793

### Measuring time complexity in the length of the input v/s in the magnitude of the input

There are two good answers already, but there are two points that weren't touched on. One is that of output-polynomial time. A lot of theoretical CS concerns itself purely with decision problems, ...
• 923
Accepted

### Protein folding, P vs. NP, and DeepMind with AlphaFold

The $\mathsf{P}$ vs. $\mathsf{NP}$ problem asks whether $\mathsf{P}=\mathsf{NP}$. To settle this problem one needs to either provide a formal proof that $\mathsf{P}=\mathsf{NP}$ or a formal proof that ...
• 28.2k

### How to prove greedy algorithm is correct

There is a very nice theory on when greedy algorithms work in general. It is based on the abstract concept of matroids. A detailed explanation is given by Jeremy Kun.
• 13.9k

### Design and analyze an efficient algorithm that, given n distinct integers, returns an element which is neither the smallest nor the largest

Straight forward and simple solution- 1)Randomly select any three integers from the list ,say p,q,r. 2)Return the element which is not maximum and minimum among p,q,r. Since all elements in the given ...
• 29
Accepted

• 12.5k
Accepted

### Describing the set of Running Time of all Turing Machines

It is not possible to describe the subset of functions that represent the running time of valid Turing machines in terms of pure mathematics, without reference to the concept of a Turing machine. This ...
Accepted

### Question about step in proof that predecessor subgraph forms a breadth-first tree

Your update is correct. On first reading I thought it was wrong because distances can be negative. It's early here for me ... then I remembered that CLRS defines distance from $s$ to $v$ to be the ...
• 36
1 vote

### Proving the correctness of a greedy algorithm for the Circular Scheduling Problem

Your algorithm is not correct. Consider intervals [1,7], [8, 14], [15, 21], [22,28], [13,16], [2,9], [3,10], [4,11], [17,23], [18,24], [19, 25]. Your algorithm chooses [13,16] first, as it only ...
1 vote
Accepted

### Ways to speed up a Recursive Backtracking Algorithm

I think you pretty much got it there. There really aren't many ways to improve it, our best method is a slow one! (though our human brains instinctively would love to find something better for such a ...
1 vote

### How branching factor affects complexity of Monte Carlo Tree Search?

Monte-Carlo Tree Search is not an exhaustive search algorithm. It just does a certain amount of iterations, and then it is done. The branching factor has a (dramatic) influence on the size of the ...
• 12.7k
1 vote

### Justification for the properties of algorithmic recurrences in 'Introduction to Algorithms' (CLRS, 4e)

The 1st property is referring to the time needed by the recursive algorithm to solve a problem instance with size $n<n_0$. Under this case the algorithm can directly solve the problem, i.e. no ...
• 2,600
1 vote
Accepted

### First-Fit-Decreasing algorithm packs items of size at most 1 into bins of capacity 2

Suppose we have used First-Fit-Decreasing algorithm to open $\ell$ bins. Consider any used bin except the last one. Name it $B$. Consider the moment the total piece size of $B$ became greater than $1$,...
• 38.6k
1 vote
Accepted

### SAT polynomial time

In general, asymptotic complexity concerns itself with the size of the input. In this case, the number of input symbols. SAT is thus not polynomially solvable in the worst case as a function of the ...
• 267
1 vote
Accepted

### Chistofides' algorithm for the traveling salesman problem with relaxed triangle inequality

It is possible to get a bound of OPT + 0.5C * OPT assuming that the cost of the MST is less or equal than OPT and that the cost of the perfect matching is at most 0.5C * OPT which can done by ...
1 vote

### Measuring time complexity in the length of the input v/s in the magnitude of the input

You are correct; time complexity in theoretical computer science is usually measured in terms of the size of the input1. This imposes a wrinkle for working programmers using time complexity to reason ...
• 1,674
1 vote

### Describing the set of Running Time of all Turing Machines

Short answer: No. These are called the time constructible functions. The definition is basically what you would expect it to be: a function $f(n)$ is fully time constructive if there is a Turing ...
• 156k

Only top scored, non community-wiki answers of a minimum length are eligible