9
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.
- 81.4k
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 ...
- 27.8k
8
votes
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 ...
- 274k
8
votes
Accepted
What is the average-case complexity of trial division?
By the prime number theorem, about a $1/\log(n)$ fraction of numbers in the range $[n/2,n]$ are prime. We know that the algorithm will take $\Theta(\sqrt{n})$ time for each of them (since for all $x \...
D.W.♦
- 154k
7
votes
What is the average time complexity, for a single linked list, for performing an insert?
Either if you want to insert at the end of the list or at the beginning of the list, you're going to have $O(1)$ Complexity for that and $O(1)$ space.
If you want to insert at the beginning of the ...
- 181
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 ...
- 9,727
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(...
- 274k
4
votes
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 ...
- 5,359
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 ...
- 9,027
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
$$
\...
- 274k
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,202
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 ...
- 13.9k
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 ...
- 171
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 ...
- 274k
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 ...
- 274k
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"....
- 71.9k
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: ...
- 507
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$.
D.W.♦
- 154k
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+...
- 7,365
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.♦
- 154k
2
votes
What is the time complexity of this atrocious algorithm?
Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:
$\qquad\begin{align*}
T(\mathtt{[] | [x]}) &= d, \\
T(\...
- 71.9k
2
votes
What is the time complexity of this atrocious algorithm?
I was not careful and assumed a standard implementation of minimum, not the one given in the question. Hence, the answer below solves a much simpler problem.
...
- 71.9k
2
votes
Accepted
Average depth of a Binary Search Tree and AVL Tree
True, the height any fixed tree can range from logaritmic to linear (in terms of the number of nodes). The avarage depth of the nodes ranges correspondingly. So, trees can range from good (logaritmic) ...
- 29.6k
2
votes
Average depth of a Binary Search Tree and AVL Tree
These are balanced trees. That means, the algorithm for adding / removing elements from it provides that the difference of the depth of the subtrees remains below a (low) limit.
These trees are also ...
- 416
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.♦
- 154k
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
...
2
votes
How do you express the theorem statement about unsuccessful search on average-case for unsuccessful searches in hashing with quantifiers?
The average-case running time (or expected running time) of a randomized algorithm is typically defined to be the expectation of the running time of the algorithm, with respect to the random coins ...
D.W.♦
- 154k
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 ...
- 293
Only top scored, non community-wiki answers of a minimum length are eligible