78
votes
Accepted
Order of growth definition from Reynolds & Tymann
The paragraph is wrong. Unfortunately, it looks exactly like the kind of thing that a student who does not understand the material would write as an answer to an exercise. This sort of nonsense has no ...
- 81.4k
61
votes
Accepted
How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case?
This algorithm can be re-written like this
Scan A until you find an inversion.
If you find one, swap and start over.
If there is none, terminate.
Now there can be ...
- 72k
44
votes
Accepted
Will hardware/implementation affect the time/space complexity of algorithms?
Sure. Certainly. Here's how to reconcile your discomfort.
When we analyze the running time of algorithms, we do it with respect to a particular model of computation. The model of computation ...
D.W.♦
- 156k
41
votes
How to prove greedy algorithm is correct
Ultimately, you'll need a mathematical proof of correctness. I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a ...
D.W.♦
- 156k
37
votes
Accepted
Are there any functions with Big O (Busy Beaver(n))?
The usual meaning of algorithm is a program that always halts. Under this definition, no algorithm has a running time of $\Theta(\mathit{BB}(n))$, or indeed $\Omega(\mathit{BB}(n))$. Indeed, such an ...
- 275k
34
votes
How is algorithm complexity modeled for functional languages?
If you assume that the $\lambda$-calculus is a good model of functional programming languages, then one may think: the $\lambda$-calculus has a
seemingly simple notion of
time-complexity: just count
...
- 8,308
31
votes
Accepted
How long does the Collatz recursion run?
This is Collatz conjecture - still open problem.
Conjecture is about proof that this sequence stops for any input, since this is unresolved, we do not know how to solve this runtime recurrence ...
- 9,425
25
votes
Accepted
Does space complexity analysis usually include output space?
Typically, we consider space complexity in terms of Turing machines with:
one read-only input tape
one write-only output tape
however many read-write working tapes you want.
The space usage is the ...
- 81.4k
23
votes
How is algorithm complexity modeled for functional languages?
Algorithm complexity is designed to be independent of lower level details.
No, not really. We always count elementary operations in some machine model:
Steps for Turing machines.
Basic operations on ...
- 72k
22
votes
Accepted
Why don't we use quick sort on a linked list?
The memory access pattern in Quicksort is random, also the out-of-the-box implementation is in-place, so it uses many swaps if cells to achieve ordered result.
At the same time the merge sort is ...
- 9,425
20
votes
Accepted
Time complexity of addition
If your algorithm uses asymptotically less than $n$ time, then it does not have enough time to read all the digits of the numbers it is adding. You are to imagine you are handling very large numbers (...
- 4,282
20
votes
Accepted
Explaination for Variation of Boyer-Moore Majority voting algorithm
Here is a different way to consider the same algorithm, or rather its general form with $k$ counters (in your case, $k=2$). There are $k$ "containers" and a trash bag. Each container will contain one ...
- 275k
20
votes
Accepted
Can I multiply Big-O time complexities?
Yes, you can and yes, it is.
Considering, for example, the non-negative case, we have a more general property:
$$O(f)\cdot O(g) = O(f\cdot g )$$
Let's take $ \varphi \in O(f) \cdot O(g) $. Then we ...
- 2,364
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
18
votes
Accepted
Why not to take the unary representation of numbers in numeric algorithms?
What this means is that unary knapsack is in P. It does not mean that knapsack (with binary-encoded numbers) is in P.
Knapsack is known to be NP-complete. If you showed that knapsack is in P, that ...
D.W.♦
- 156k
17
votes
Accepted
Why is adding log probabilities faster than multiplying probabilities?
Also, the Wikipedia page (https://en.wikipedia.org/wiki/Log_probability) is confusing in this respect, stating "The conversion to log form is expensive, but is only incurred once." I don't understand ...
- 646
17
votes
Accepted
"Guess the number" Problem on Turing machines
Yes, it is pointless and absurd to implement an algorithm to "guess the number" using the most common kind of Turing machine, whose head can read any cell on the tape, since, as you pointed ...
- 38.6k
16
votes
How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect
2D local maximum
input: 2-dimensional $n \times n$ array $A$
output: a local maximum -- a pair $(i,j)$ such that $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value. ...
- 501
16
votes
Accepted
Why is the dynamic programming algorithm of the knapsack problem not polynomial?
When we say polynomial or exponential, we mean polynomial or exponential in some variable.
$nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a ...
- 13.2k
16
votes
Accepted
A* graph search time-complexity
These are basically two different perspectives or two different ways of viewing the running time. Both are valid (neither is incorrect), but $O(b^d)$ is arguably more useful in the settings that ...
D.W.♦
- 156k
16
votes
Accepted
What does it mean by saying "Asymptotically more efficient"?
First off, both algorithms "work" for all inputs. The question is about performance.
The answers to that question are kind of crappy. One way to say one algorithm is asymptotically more efficient ...
16
votes
Accepted
What's the Big O runtime of a DFS word search through a matrix?
The complexity will be $O(m*n*4^{s})$ where m is the no. of rows and n is the no. of columns in the 2D matrix and s is the length of the input string.
When we start searching from a character we ...
- 1,195
16
votes
Why aren't primality tests easily linear in time complexity?
It seems that the main sticking point of the question here is: Why express runtime in terms of the size of the input, rather than the numeric value that the input represents? And indeed in some cases ...
- 261
15
votes
How long does the Collatz recursion run?
You translated the code correctly. There are many methods for solving recurrences.
However, it is currently unknown if collatz even halts for all ...
- 72k
15
votes
What are the flaws in this encryption algorithm?
This is not a secure encryption scheme. It is similar to a Hill cipher, and vulnerable to similar attacks. For instance, it is vulnerable to known-plaintext attacks: an attacker who observes a ...
D.W.♦
- 156k
15
votes
Accepted
What is the intuition behind Strassen's Algorithm?
The real answer to this question is that if you play with it long enough, you'll hit an algorithm requiring 7 multiplications – not necessarily the same as Strassen's, but an equivalent one, in a ...
- 275k
14
votes
how to calculate time complexity of non terminating loops
If the program runs forever, its running time is infinite. So, if it always enters an infinite loop, its running time is infinite.
This is a degenerate case. Normally we focus only on algorithms ...
D.W.♦
- 156k
14
votes
How to prove greedy algorithm is correct
I will use the following simple sorting algorithm as an example:
...
- 5,931
14
votes
Find largest and second largest elements of the array
Here I present an optimal solution minimizing the number of comparisons.
The thing to take advantage of is the first step of the original algorithm:
...
- 4,431
13
votes
How long does the Collatz recursion run?
The time complexity function is
\begin{cases}
T(n)= O(1) \text{ for } n\le 1\\
T(n)=T(n/2) + O(1) \text{ for } n\text{ even}\\
T(n)=T(3n+1) + O(1)\text{ for } n\text{ odd}\\
\end{cases}
which can be ...
- 4,807
Only top scored, non community-wiki answers of a minimum length are eligible