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

### What is the time complexity of this atrocious algorithm?

We can write a recurrence relation for this procedure as follows. Let $T(n)$ be the worst-case time for running sort on a list of length $n$. When calling ...
Accepted

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

If you have no additional requirements on the contents of the list, you can just insert the item at the head, which is O(1). If you do (e.g. the list must be kept sorted or deduplicated), insertion ...

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

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 $$\... 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 ... 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 ... 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 ... 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 ... 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 ... 3 votes ### How do you express the theorem statement about unsuccessful search on average-case for unsuccessful searches in hashing with quantifiers? There are two prominent uses of the term "average" in algorithm analysis. Average-case as a special case of expected costs Here, "average case" just means "expected case w.r.t. uniform distribution".... 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: ... 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, ... 3 votes Accepted ### How is this algorithm average case derived? The sum n+(n-1)+\dots + 3+2+1 evaluates to n(n+1)/2 (it's the so-called Gauss sum). Now divide by n, you and get (n+1)/2. 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+...
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 ...