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.1k
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 ...
- 71.8k
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.♦
- 152k
38
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.♦
- 152k
36
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 ...
- 274k
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,268
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,385
24
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.1k
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 ...
- 71.8k
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,385
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,356
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,777
19
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,237
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.♦
- 152k
18
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 ...
- 274k
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.2k
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.1k
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.♦
- 152k
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 ...
- 11.9k
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,185
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 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. ...
- 491
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 ...
- 71.8k
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.♦
- 152k
15
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 ...
- 626
14
votes
Accepted
Difference between time complexity and computational complexity
Computational complexity is just a more general term, as time is not the only resource we might want to consider. The next most obvious is the space that an algorithm uses, and hence we can talk about ...
- 17.9k
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.♦
- 152k
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,391
13
votes
Accepted
If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?
You ask,
I have an $O(2^n)$ runtime, why do I not observe $2^n$ recursive calls for $n=15$?
There are many things wrong in the implied conclusion.
$O(\_)$ only gives you an upper bound. The true ...
- 71.8k
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,787
Only top scored, non community-wiki answers of a minimum length are eligible