The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
1answer
158 views

What is the expected number of nodes at depth d of a tree after i random insertions

Suppose one wanted to build a tree at random. Let the first insertion at step $i = 1$ be the root node. From here, nodes are inserted into the tree at random one at a time. How would one go about ...
3
votes
1answer
65 views

Algorithm Analysis: Expected Running Time of Recursive Function Based on a RNG

I am somewhat confused with the running time analysis of a program here which has recursive calls which depend on a RNG. (Randomly Generated Number) Let's begin with the pseudo-code, and then I will ...
3
votes
1answer
55 views

Compare asymptotic WC runtime with measured AC runtime

I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations. But this is the worst ...
3
votes
2answers
80 views

Genetic algorithm: What is the expected number of strings that are explored?

My question concerns genetic algorithm searching along bit strings. Given: $N$ = population size $l$ = length of bit strings $p_c$ = probability that a single crossover occur (double crossover ...
0
votes
1answer
84 views

Basics of Amortised Analysis

I cannot really find a source that does not use the same examples provided by CLRS. I need a simpler example than MULTI-POP example. Could someone provide an ...
0
votes
1answer
44 views

Pentary Search Recurrence Relation

I have done an assignment question which asks me to find the average case of pentary search. The one I came up with is: C(n) = C(n/5) + 14/5 However, I got it ...
5
votes
2answers
234 views

Complexity of keeping track of $K$ smallest integers in a stream

I need to analyze the time complexity of an online algorithm to keep track of minimum $K$ numbers from a stream of $R$ numbers. The algorithm is Suppose the $i$th number in the stream is $S_i$. ...
5
votes
1answer
62 views

Completeness of formal definition of 'hardness on the average'

While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for ...
1
vote
1answer
153 views

Closed-form Expression of the Expected value of the Cost of D&C Algorithm?

Let there is a binary-string, $B$, of length $N$. The probability of occurrence of 0 and 1 in this binary-word is $p$ and $q$ , respectively. Each bit in the string is independent of any other bit. ...
6
votes
1answer
93 views

Can expected “depth” of an element and expected “height” differ significantly?

When analysing treaps (or, equivalently, BSTs or Quicksort), it is not too hard to show that $\qquad\displaystyle \mathbb{E}[d(k)] \in O(\log n)$ where $d(k)$ is the depth of the element with rank ...
2
votes
1answer
157 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
121 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 ...
2
votes
1answer
2k 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 ...
3
votes
1answer
1k 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
252 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. ...
10
votes
0answers
201 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
2k 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 ...
6
votes
3answers
5k views

Evaluating the average time complexity of a given bubblesort algorithm.

Considering this pseudo-code of a bubblesort: ...