20
votes
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
8
votes
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
4
votes
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
4
votes
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
4
votes
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
3
votes
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
3
votes
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
2
votes
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
2
votes
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
2
votes
Accepted
What recurrence describes the time complexity of this algorithm?
Partial answer: The problem admits an $O(n^{\log_3(2)}) \leq O(n^{0.631})$ algorithm.
The algorithm $\mathcal A$ works as follows:
Query $x = A[n/3]$ and $y = A[2n/3]$.
If $x = y$, return $\max \{x, \...
- 1,516
2
votes
Prove that the problem MATCH is NP-complete
Let $\phi = c_1 \wedge c_2 \wedge \dots c_m$ be a 3-SAT formula on $n$ variables $x_1, \dots, x_n$, where $c_i$ is the $i$-th clause.
Assume w.l.o.g. that no clause contains both a literal and its ...
- 28.2k
2
votes
How do I solve this recurrence equation?
To resolve $$T(n)=T(\tilde{a}n)+n$$
you can apply the Master
Theorem(https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)):
the recurrence:
\begin{equation}
T(n)
= \begin{...
2
votes
Accepted
Geometric Set Cover in one dimension
Consider $x_1, …, x_n\in \mathbb{R}$ and $I_1, …, I_k$ be intervals, $I_i = [a_i, b_i]$.
Suppose without loss of generality that $x_1 < x_2 < … < x_n$. Let $I_i$ be an interval such that $x_1 ...
- 12.5k
2
votes
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 ...
- 83
2
votes
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,188
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 ...
- 26
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 ...
D.W.♦
- 156k
Only top scored, non community-wiki answers of a minimum length are eligible