# Tag Info

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 ...
• 9,837
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 ...
• 72.4k
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 ...
• 159k

### 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
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,455

### 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 ...
• 3,182

### 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 ...
• 72.4k
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 ...
• 7,068
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 ...
• 159k
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 ...
• 9,837
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
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,215

### 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 ...

### 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 ...
• 22.1k

### 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 ...
• 72.4k

### 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 ...
• 159k
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)$ ...
• 81.7k

### 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,817

### 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 ...
• 231
Accepted

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

Consider the following (silly) function cow, which accepts a number $n$: ...
• 30.4k
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 ...
• 13.2k
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 ...
• 386
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 ...
• 277k
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, ...
• 1,483
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)$ ...
• 277k
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 ...
• 277k

### 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 ...
• 201

### 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\...
• 81.7k