The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
11 views

how to calculate the average case efficiency of the improved bubble sort? [duplicate]

I already know that the average case efficiency for this algorithm is: $\Theta(n^2)$. But I want to know how to obtain this result. This is the algorithm that I have: ...
4
votes
3answers
82 views

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

A comparison sort cannot require fewer than $\Theta (n\log n)$ comparisons on average. However, consider this sorting algorithm: ...
0
votes
1answer
110 views

Average Time Complexity of Searching An Array [closed]

Why is the average time complexity of searching an array $O(n)$? Is it because if the element does not exist, then $n$ searches must be done. If the element is at the end of the array then $n$ must ...
1
vote
0answers
37 views

Given an algorithm, what are the probabilities for its run-time cases?

I am given this algorithm And I am also given the fact that $1 \leq k \leq n$. If we let X be the number of times line 2 is executed, then I am supposed to find the run-time probabilities for the ...
3
votes
1answer
120 views

Counting nodes in a trie

I'm studying random tries in one of my classes, and was wondering if anyone could offer any guidance regarding a problem. Question: Given a random $m$-ary trie with $n$ total leaves, letting $I$ be ...
3
votes
1answer
51 views

Asymptotic expected runtime of Randomized Algorithm

I am analyzing the asymptotic runtime of a randomized algorithm in expectation. The algorithm has the following properties: Given input size $n$, with probability $3/4$ it moves on to solve an ...
0
votes
0answers
55 views

What is the average runtime of appending items to arrays?

It is the time of the year again in colleges for final exams and I am preparing mine as of now and I am finding myself in hot water when it comes to understanding the running times of appending items ...
0
votes
0answers
17 views

Expected number of collisions, 2 different solutions, what makes the difference?

The first solution: The probability that a slot is not mapped to on a single insert is $1-\frac{1}{m}$, and the probability it is not mapped to after $n$ inserts is $(1-\frac{1}{m})^n$. So the ...
3
votes
1answer
49 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
3k 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
43 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
84 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
46 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, ...
2
votes
4answers
165 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
266 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
147 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
66 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
109 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
324 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
51 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
294 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$. ...
6
votes
1answer
76 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
231 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
104 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
170 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
132 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 ...
5
votes
1answer
4k 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
3answers
3k 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
557 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
269 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
4k 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 ...
8
votes
3answers
9k views

Evaluating the average time complexity of a given bubblesort algorithm.

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