Share Your Experience: Take the 2024 Developer Survey

# Tag Info

### 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.
• 81.8k
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 ...
• 30.4k
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 ...
• 9,837

• 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 ...
• 278k
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 ...
• 30.4k

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