11
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.
- 82.2k
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 ...
- 31.6k
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,885
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(...
- 279k
5
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 ...
- 181
5
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 ...
- 14.1k
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
$$
\...
- 279k
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,272
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 ...
- 279k
3
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; ...
- 31.6k
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.♦
- 166k
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,604
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$, ...
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 ...
- 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.♦
- 166k
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
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$...
- 14.9k
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 ...
- 72.9k
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 ...
- 279k
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}$ ...
- 2,542
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 ...
- 2,389
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\...
- 29.6k
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 ...
- 542
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(...
- 29.6k
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 ...
- 279k
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 ...
- 31.6k
1
vote
Accepted
Average-case complexity of linear search where half of the elements in the array are duplicates
Let us assume the elements in the array are the multi-set $M=\{1,2,\cdots,n-k, d, d, \cdots, d\}$, where $d$, an element that is different from $1,2,\cdots, n-k$, appears $k\ge 0$ imes. The situation ...
- 39.1k
1
vote
Accepted
Finding the average time complexity for a max algorithm
Let $\small n = \mathsf{len}(L)$ and $\small t_n$ be the times that $\small \mathsf{max}$ is assigned a value. For $\small 0 \leq i < n$, define a random variable $\small X_i$ as
$$
\small
X_i = \...
- 816
Only top scored, non community-wiki answers of a minimum length are eligible