87 votes
Accepted

Why is the log in the big-O of binary search not base 2?

When you change the base of logarithm the resulting expression differs only by a constant factor which, by definition of Big-O notation, implies that both functions belong to the same class with ...
fade2black's user avatar
  • 9,837
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
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

Checking equality of integers: O(1) in C but O(log n) in Python 3?

Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit. Not quite. C ints are machine-word-sized and ...
Alexey Romanov'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
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
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

Are there any algorithms or data structures that need to find the median value of a set?

if there are any practical applications of this algorithm in the domain of computer science besides being a theoretical improvement The application of this algorithm is trivial - you use it whenever ...
fade2black's user avatar
  • 9,837
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'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

Checking equality of integers: O(1) in C but O(log n) in Python 3?

Complexity is defined relative to a computation model. P and NP, for example, are defined in terms of Turing machines. For comparison, consider the word RAM model. In this model, memory is divided ...
Pseudonym's user avatar
  • 22.1k
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
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
Accepted

Is "super-exponential" a precise definition of algorithmic complexity?

"Super-exponential" just means more than exponential, so a function is super-exponential if it grows faster than any exponential function. More formally, this means that it is $\omega(c^n)$ ...
David Richerby's user avatar
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

Are there any algorithms or data structures that need to find the median value of a set?

Median filtering is common in reduction of certain types of noise in image processing. Especially salt and pepper noise. It works by picking out the median value in each color channel in each local ...
mathreadler's user avatar
12 votes
Accepted

Why does using unary in subset sum problem result polynomial time complexity?

Consider the following (silly) function cow, which accepts a number $n$: ...
Andrej Bauer's user avatar
  • 30.4k
12 votes
Accepted

How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?

What is meant by "lower bound" in this case is a lower bound on the worst-case number of comparisons. In this case, it happens to also be an upper bound. The lower bound has to be something that is ...
Tom van der Zanden's user avatar
11 votes
Accepted

Is there really a $ O(1/n) $ algorithm?

No algorithm really has an $O(1/n)$ running time, but that notation might be used informally for an algorithm who's running time is really $O(m/n)$ where $m$ is large and not expected to vary. Here's ...
Blckknght's user avatar
  • 386
11 votes
Accepted

Why call it 'Time Complexity'?

Perhaps the earliest place in which time complexity appears is On the computational complexity of algorithms by Hartmanis and Stearns. Their goal is to study computation complexity, which they define ...
Yuval Filmus's user avatar
10 votes
Accepted

Why does merging two sorted arrays take 2N - 1 comparisons?

The question asks to show the lower bound on the number of comparisons in merging two sorted arrays of length $N$. Therefore, you need to argue that no matter what comparison-based algorithm you use, ...
Denis Pankratov's user avatar
10 votes
Accepted

Amortized time cost of insertion into an Array list

For the estimate, $$ n + \frac{n}{2} + \frac{n}{4} + \cdots +1 <n \left(1 + \frac{1}{2} + \frac{1}{4} + \cdots \right) = 2n, $$ since $1 + 1/2 + 1/4 + \cdots = 2$. If $n$ insertions take $O(n)$ ...
Yuval Filmus's user avatar
10 votes
Accepted

Skip List randomization complexity

According to the hint, the number of elements in the levels beyond the first is expected to be $$ n \cdot (1/2 + 1/4 + \cdots + 1/2^k). $$ Presumably, $k \approx \log n$, though as we will see, this ...
Yuval Filmus's user avatar
10 votes

Why is the log in the big-O of binary search not base 2?

In addition to fade2black's answer (which is completely correct), it's worth noting that the notation "$\log(n)$" is ambiguous. The base isn't actually specified, and the default base changes based on ...
MattPutnam's user avatar
10 votes

Are there any algorithms or data structures that need to find the median value of a set?

Computing medians is particularly important in randomized algorithms. Quite often, we have an approximation algorithm that, with probability at least $\tfrac34$, gives an answer within a factor of $1\...
David Richerby's user avatar
10 votes

What is the name of this search algorithm?

I do not think there is a name for that particular algorithm, but I think it will achieve similar performance to much simpler parallel algorithms for this task. In general when designing parallel ...
nosyarg's user avatar
  • 232
9 votes

What exactly is polynomial time?

Running an algorithm can take up some computing time. It mainly depends on how complex the algorithm is. Computer scientists have made a way to classify the algorithm based on its behaviour of how ...
mixdev's user avatar
  • 191

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