Skip to main content
Share Your Experience: Take the 2024 Developer Survey
10 votes

Are there NP COMPLETE problems that are "easy" in practice?

Honestly, SAT seems pretty easy in practice. SAT solvers are routinely used on instances with millions of variables that arise in model checking against formal specifications.
David Richerby's user avatar
8 votes
Accepted

Time complexity of this while loop

Worst case, if the second call to rand() returns 0 and the first call doesn't, you get a floating point division by zero, and if you are using standard IEEE 754 arithmetic, the result is +infinity. In ...
gnasher729's user avatar
  • 30.4k
7 votes
Accepted

How to prove that average complexity is N/2 for linear search in the unsorted array

First assume input is uniformly distributed. More precisely it is $\frac{n+1}{2}$. When you search for a particular element $x$ in an array of size $n$, that element may be located at the position ...
fade2black's user avatar
  • 9,837
6 votes

Time complexity of this while loop

This answer refers to a version of the question in which $x$ is sampled by dividing two random numbers. As mentioned by Rick Decker's answer, given $x$, we can approximate the running time by $O(\max(...
Yuval Filmus's user avatar
4 votes
Accepted

Confusion about the definition of the average-case running time of algorithms

The definition is a special case of a more general notion. Given probability distributions $\mu_1,\mu_2,\ldots$ on inputs, the average running time (with respect to the $\mu_i$) is defined as $$ \...
Yuval Filmus's user avatar
4 votes

Average-Case Analysis of a Simple Max-Finding Algorithm

Don Knuth recently gave a recreation of his first lecture ever given at Stanford in which he addresses precisely this question with virtually the same code structure as what you have above. True to ...
templatetypedef's user avatar
4 votes
Accepted

Why does linear search have $\frac{n}{2}$ comparisons on average?

It's neither ${(n^2+3n)}/{(2n+2)}$ nor $n/2$. In fact, the question itself doesn't make much sense at all. In order to be able to talk about the average running time of an algorithm, you have to fix a ...
quicksort's user avatar
  • 4,262
4 votes

Average Case Running Time of Quicksort Algorithm

The average case running time of quicksort satisfies the recurrence $$ T(n) = \frac{1}{n} \sum_{i=1}^n [T(i-1) + T(n-i)] + \Theta(n), $$ with base case $T(0) = \Theta(1)$. In view of solving this ...
Yuval Filmus's user avatar
4 votes

Are there NP COMPLETE problems that are "easy" in practice?

Problems which are easy to approximate, like the Euclidean Traveling Salesman problem. These are problems for which polynomial-time approximation scheme (PTAS) approximation algorithm do exist. A ...
Rexcirus's user avatar
  • 171
4 votes

Are there NP COMPLETE problems that are "easy" in practice?

That a problem is NP-complete means just that the worst case is hard. It might well be that such worst cases are extremely rare, or just don't show up in the "usual" cases of interest, and ...
vonbrand's user avatar
  • 14.1k
3 votes
Accepted

Average case of simple algorithm like binary search

The average case time complexity is $O(\log n)$ (with a suitable implementation). Intuitively, each iteration typically removes a constant factor of the elements from the array. Here's a more formal ...
D.W.'s user avatar
  • 161k
3 votes
Accepted

Average-case analysis of linear search given that the desired element appears $k$ times

Note $$ \begin{align*} E(X)&=\sum_{i=1}^{n-k+1} i \cdot \Pr(X = i)\\ &=\sum_{i=1}^{n-k+1} \sum_{j=1}^i\Pr(X = i)\\ &=\sum_{j=1}^{n-k+1} \sum_{i=j}^{n-k+1}\Pr(X = i)\\ &=\sum_{j=1}^{n-k+...
xskxzr's user avatar
  • 7,455
3 votes

Average-Case Analysis of a Simple Max-Finding Algorithm

The number of times that max is assigned to is known as the number of records (or left-to-right maxima) in the permutation. The following results are standard, and can be found in a paper of ...
Yuval Filmus's user avatar
3 votes

Average depth of a Binary Search Tree and AVL Tree

Your question refers to average depth of the nodes in a BST, but it's easiest answer this by thinking about the overall height of the tree first. In the worst case, the depth of the tree can be $n$, ...
Edward Ned Harvey's user avatar
3 votes
Accepted

How to calculate the average of x numbers?

Instead of giving an answer, I will try to paraphrase the steps, I hope this will help you solve your homework. Identify the problem: What is the input? What is the output? Comprehend the problem: ...
ilke444's user avatar
  • 507
2 votes

Confusion about the definition of the average-case running time of algorithms

Let $U_n$ be the set of all inputs of size $n$. Suppose $S_n^i$ are some partition of $U_n$ (indexed by $i$), such that each member of $S_n^i$ takes time $T(n, i)$. We can write the expected time ...
feersum's user avatar
  • 313
2 votes
Accepted

Nonuniform input distributions in average case analysis

Yes, the expected running time under some other distribution would still count as an example of average-case analysis. However, when you describe it to someone, make sure you explain what ...
D.W.'s user avatar
  • 161k
2 votes

What is the average time complexity, for a single linked list, for performing an insert?

https://www.bigocheatsheet.com considering finding (Access) the position of the element before insert as separate operation. Array: Access - O(1) // we can get the element by index directly ...
Maksym Pedych's user avatar
2 votes

Time complexity of this while loop

In general, the time taken by this snippet is mainly governed by how many times the loop iterates. In other words, how many times will you need to multiply $x$ by $0.8$ to get a result less than $0.01$...
Rick Decker's user avatar
  • 14.8k
2 votes

Trying to understand CLRS bucket sort analysis

You are asking why $\qquad\displaystyle \sum_{j=1}^{n}\sum_{k=1}^{n}X_{ij}X_{ik} \quad=\quad \sum_{j=1}^{n}X_{ij}^2 + \sum_{j = 1}^{n}\sum_{1 \leq k \leq n,\\ k \neq j}X_{ij}X_{ik}$ holds (in ...
Raphael's user avatar
  • 72.5k
2 votes
Accepted

Weighted probability using Huffman Tree

Given a distribution $\mu$ on a finite set, let us denote by $T(\mu)$ the average depth of a leaf in a Huffman tree of $\mu$ (depth is measured by the number of edges from root to leaf); we assume ...
Yuval Filmus's user avatar
2 votes

Are there NP COMPLETE problems that are "easy" in practice?

See this question: A greedy algorithm for the bottle filling problem I added a proof that this problem is NP-complete. However, practical instances of the problem will usually be quite easy to solve; ...
gnasher729's user avatar
  • 30.4k
2 votes
Accepted

Asymptotic growth of a series

$$ \begin{align*} \sum_{k=1}^{c \log n - 1} k 2^{- \frac{k}{3}} &\le \sum_{k=1}^{c \log n } k 2^{- \lfloor \frac{k}{3} \rfloor } \le \sum_{k=1}^{\lceil \frac{c}{3} \log n \rceil} 3k 2^{-k+1} \le 6\...
Steven's user avatar
  • 29.5k
2 votes
Accepted

Trouble finding average case of a find max algorithm

Let me start with your main question "where my mistake took place exactly?" - in short, the whole point is in the wrong choice of the probability distribution for $Pr(t_n=t)$. You are ...
zkutch's user avatar
  • 2,364
2 votes

Trouble finding average case of a find max algorithm

If the maximum element is the $n$'th, then $\text{maxNum}$ is not necessarily updated n times. Consider for example the case where the second largest element is in first position. Then $\text{maxNum}$ ...
Tassle's user avatar
  • 2,522
2 votes

What is a sorting algorithm that is robust to a faulty comparison?

I think I've thought up a solution. First, do a first pass with any decent sorting algorithm you want (like quicksort), which should, at worst, result in only one item that's significantly far from ...
chausies's user avatar
  • 532
2 votes
Accepted

Average case complexity and Big-O

Wikipedia use is correct. The notation $O(\cdot)$ denotes a set of function, in particular $O(f(n))$ contains all functions $g(n)$ for which there is a constant $c$ and a choice of $n_0$ such that $g(...
Steven's user avatar
  • 29.5k
1 vote
Accepted

Average Case Analysis of Insertion Sort as dealt in Kenneth Rosen's "Discrete Mathemathematics and its Application"

The probability $1/i$ is correct, since it refers to the relative order of $a_1,\ldots,a_i$ before sorting the first $i-1$ elements. However, the argument seems wrong. The relevant probability is not ...
Yuval Filmus's user avatar
1 vote

How to estimate the average time complexity of greatest common divisor?

If you start wit a pair (a, b), a>=b, one step goes to (b,a’) with a’ < a/2. This gives an easy upper bound for the number is steps. You can analyse two steps from (a, b) to (a’, b,’) and get a ...
gnasher729's user avatar
  • 30.4k

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