13 votes
Accepted

Proving that the average case complexity of binary search is O(log n)

I think most text book will provide you a good proof. For me, I can show the average case complexity as follows. Assuming a uniform distribution of the position of the value that one wants to find ...
user avatar
  • 839
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 ...
user avatar
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 \...
user avatar
  • 141k
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 ...
user avatar
  • 25.2k
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 ...
user avatar
7 votes
Accepted

Understanding Expected Running Time of Randomized Algorithms

There are two notions of expected running time here. Given a randomized algorithm, its running time depends on the random coin tosses. The expected running time is the expectation of the running time ...
user avatar
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 ...
user avatar
  • 9,612
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(...
user avatar
4 votes

What is the difference between expected cost and average cost of an algorithm?

In short, the average is the expected value of the uniform distribution. If $T(x)$ denotes the runtime of some algorithm on input $x \in \mathcal{X}$, then the expected runtime for input size $n$ is $\...
user avatar
  • 70.9k
4 votes
Accepted

Why does this mergesort variant not do Θ(n) comparisons on average?

Since you don't do any reordering while splitting, the length of array after the while loop can not be larger than the length of ...
user avatar
  • 70.9k
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 ...
user avatar
  • 4,676
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 ...
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 ...
user avatar
  • 4,132
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 $$ \...
user avatar
4 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.
user avatar
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 ...
user avatar
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"....
user avatar
  • 70.9k
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$.
user avatar
  • 141k
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 ...
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: ...
user avatar
  • 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$, ...
user avatar
3 votes

Counting nodes in a trie

If you don't have any degree-1 nodes in your trie (which is a tree) than you have more leaves than interior nodes. So in this case you have $I\le n $. It depends a bit how you define the trie whether ...
user avatar
  • 11.9k
3 votes

Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data

Here is a similar recent example due to Mossel et al. There are $n$ vertices which are partitioned randomly into two classes. Two vertices of the same type are connected with probability $p$, and two ...
user avatar
3 votes
Accepted

Where would someone find amortized analysis more useful than average analysis and the opposite?

The two are not mutually exclusive. In most situations you're interested in amortized analysis, since usually operations are fast enough so that no user would notice a one time long running time, the ...
user avatar
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+...
user avatar
  • 7,250
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 ...
user avatar
  • 141k
2 votes
Accepted

On "The Average Height of Planted Plane Trees" by Knuth, de Bruijn and Rice (1972)

The monotonic paths from $(−h,h)$ to $(n−1,n−1)$ that you construct only avoid the boundary $y=x+2h+1$ before they cross $y=x+h$ for the first time. Thus the formula you use is not applicable.
user avatar
  • 6,519
2 votes
Accepted

Find $k$ subsets containing a particular element quickly

Use a hash table, keyed on elements of $U$. For each subset $S$ of $U$, say $S=\{x_1,\dots,x_\ell\}$, you'll add $S$ to the hash table $\ell$ times, once for key $x_1$, once for key $x_2$, and so on. ...
user avatar
  • 141k
2 votes
Accepted

Average Time Complexity of Searching An Array

It sounds like you're talking about a linear search. If we assume that the key is equally likely to be in any of the $n$ locations in the array, then the expected location is $\frac{n+1}{2}$. A ...
user avatar

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