The average-case tag has no wiki summary.
2
votes
1answer
114 views
How to get expected running time of hash table? [duplicate]
If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in ...
3
votes
2answers
109 views
Hardness of finding a true or a false assignment into a generic boolean formula?
I read some research that analyzes the hardness of SAT solving in the average case.
In fact, for a 3CNF formula if you compute the ratio of clause to variables there is an interval (more or less ...
0
votes
1answer
327 views
Proof that a randomly built binary search tree has logarithmic height
How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don't ...
2
votes
1answer
415 views
Average number of comparisons to locate item in BST
This is a GRE practice question.
If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items ...
2
votes
2answers
130 views
How to go about working the average case run time of this trivial algorithm (and other algorithms)?
This is a similar algorithm to one I used in a previous question, but I'm trying to illustrate a different problem here.
...
7
votes
0answers
152 views
On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)
I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
9
votes
1answer
916 views
Expected number of swaps in bubble sort
Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i < n$. I have to find the expected number of swaps that ...
4
votes
3answers
2k views
Evaluating the average time complexity of a given bubblesort algorithm.
Considering this pseudo-code of a bubblesort:
...
