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 ...
Raphael's user avatar
  • 72.4k
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.'s user avatar
  • 159k
42 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.'s user avatar
  • 159k
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 ...
Yuval Filmus's user avatar
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 ...
Martin Berger's user avatar
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 ...
Evil's user avatar
  • 9,455
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 ...
David Richerby's user avatar
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 ...
Raphael's user avatar
  • 72.4k
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 ...
Evil's user avatar
  • 9,455
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 (...
Lieuwe Vinkhuijzen's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
zkutch's user avatar
  • 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 ...
Caleb Stanford's user avatar
17 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. ...
Neal Young's user avatar
17 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.'s user avatar
  • 159k
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 ...
md5's user avatar
  • 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 ...
John L.'s user avatar
  • 39k
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 ...
Tom van der Zanden's user avatar
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 ...
Derek Elkins left SE's user avatar
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 ...
Navjot Singh's user avatar
  • 1,215
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 ...
Flight Odyssey's user avatar
16 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 ...
Yuval Filmus's user avatar
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 ...
Raphael's user avatar
  • 72.4k
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.'s user avatar
  • 159k
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.'s user avatar
  • 159k
14 votes

How to prove greedy algorithm is correct

I will use the following simple sorting algorithm as an example: ...
adrianN's user avatar
  • 5,951
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: ...
ryan's user avatar
  • 4,511
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 ...
Sarvottamananda's user avatar
13 votes
Accepted

Looping and branching with Algorithmic Differentiation

AD supports arbitrary computer programs, including branches and loops, but with one caveat: the control flow of the program must not depend on the contents of variables whose derivatives are to be ...
Markus Mottl's user avatar

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