The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
32 views

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

I'm trying to understand the difference between these two. They both look at what happens on average, however amortized analysis is actually dealing with exactly the amount of operations you are doing ...
0
votes
1answer
43 views

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

I know that the both the average and worst case complexity of binary search is O(log n) and I know how to prove the worst case complexity is O(log n) using recurrence relations. But how would I go ...
4
votes
1answer
22 views

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

So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces ...
2
votes
1answer
46 views

Understanding Expected Running Time of Randomized Algorithms

I want to understand the expected running time and the worse-case expected running time. I got confused when I saw this figure (source), where $I$ is the input and $S$ is the sequence of random ...
2
votes
1answer
37 views

Find $k$ subsets containing a particular element quickly

Suppose there are $n$ subsets of $U$. I want to quickly (in terms of average-case) find k $ (< n)$ subsets that contain $e \in U$ (call this Extraction(e)). Elements are integers. To that effect, ...
1
vote
4answers
94 views

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

While going through probabilistic/average analysis of an algorithm, I found written somewhere that average cost and expected cost are same. Can anyone please tell me what does exactly expected cost ...
5
votes
1answer
199 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
93 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
62 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
97 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
156 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
48 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
262 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
66 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
175 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
97 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
163 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
124 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 ...
4
votes
1answer
3k 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
2k 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
354 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. ...
12
votes
1answer
241 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
3k 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 ...
7
votes
3answers
6k views

Evaluating the average time complexity of a given bubblesort algorithm.

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