# Questions tagged [average-case]

The tag has no usage guidance.

63 questions
Filter by
Sorted by
Tagged with
0answers
32 views

### Proof of the average case of the Heap Sort algorithm

Consider the following python implementation of the Heap Sort algorithm: ...
1answer
32 views

### Average Case Running Time of Quicksort Algorithm

From this website, it states that the average case of Quicksort algorithm is T(n) = T(n/9) + T(9n/10) + θ(n) Im a bit confused. Is it supposed to be ? ...
2answers
93 views

### Are there NP COMPLETE problems that are “easy” in practice?

NP COMPLETE problems are hard in the worst case (assuming $P \neq NP$). What that means is that for every polynomial $p$, sufficiently large integer $n$, and algorithm $A$, there is an instance $x$ of ...
0answers
55 views

### Upper bound on the average-case runtime of shell sort

I found that shell sort with the gaps of Fibonacci sequence has the lower bound complexity $\Omega(N \log N)$ in average cases. I want to know the upper bound complexity in average cases, so I write ...
1answer
75 views

1answer
122 views

### Trying to understand CLRS bucket sort analysis

I'm trying to understand the analysis of bucket sort in CLRS. Specifically, equation 8.2 that states: $$E[{n_i^2}] = 2 - \frac{1}{n}$$ To prove, CLRS: Random variable denoting number of elements ...
1answer
294 views

### Finding the average time complexity for a max algorithm

I'm trying to find the average-case number of times that max is assigned a value by the below algorithm find_max. ...
2answers
95 views

### Good reference for average-case runtime analysis of QuickSort

I'm a beginner in programming with little knowledge about the technicalities. I'm assigned to do a "reading project" on the average case analysis of quicksort. I mean I have to present it in class. ...
1answer
367 views

### Comb sort average complexity

The wikipedia page about comb sort claims that the average complexity of comb sort is Omega(n^2/2^p) where p is the number of increments. Take as example an uniform distributed array of 1000 elements, ...
1answer
6k views

### How to prove that average complexity is N/2 for linear search in the unsorted array [duplicate]

All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the ...
1answer
62 views

### Is this a correct approch of finding expected runtime of an algorithm?

Consider two algorithms; we analysis their run time only by counting the number of comparisons ...
3answers
2k views

### Time complexity of this while loop

So, i would like to know the time complexity of the following codes: ...
1answer
220 views

### Is quick sort the best algorithm in average case compared to other comparison-based sorting algorithms? [duplicate]

I know that quick sort has an average case of O(nlogn). And I also know that the average case of comparison-based sorting algorithms are Omega of nlogn. Can we say that quick sort is the best sorting ...
0answers
21 views

### steps to perform average case analysis [duplicate]

What are the steps required to perform average case analysis? Basically, how do you attempt average case analysis? There exists a series of steps that need to be taken to perform it right? I am ...
3answers
164 views

### Confusion about the definition of the average-case running time of algorithms

In this lecture note, The average-case running time is defined by the expected value, over all inputs $X$ of a certain size, of the algorithm's running time for $X$: T_{\text{average-case}}(n) ...
2answers
905 views

### Why does linear search have $\frac{n}{2}$ comparisons on average?

I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $\frac{n}{2}$ comparisons. I tried working this out on my own. First I considered the number of cases. ...
1answer
168 views

### How to calculate the average of x numbers? [closed]

I just started a college course and I'm being asked for a flowchart where I explain how to calculate the average of x quantity of numbers. For this assignment I'm asked to follow the problem solving ...
0answers
277 views

### Partition algorithm average-case complexity analysis

I was given the following algorithm: ...
1answer
53 views

### Nonuniform input distributions in average case analysis

When we perform average case analysis of algorithms, we assume that the inputs to the algorithm are sampled uniformly from some underlying space. For example, the average case analysis of quicksort ...
2answers
565 views

### Average-Case Analysis of a Simple Max-Finding Algorithm

Given this piece of code: ...
2answers
268 views

### How do you express the theorem statement about unsuccessful search on average-case for unsuccessful searches in hashing with quantifiers?

I was reading CLRS and in theorem 11.1 it states: In a hash table in which collisions are resolved by chaining, an unsuccessful search takes average-case time $\Theta( 1 + \alpha )$, under the ...
1answer
439 views

### Average Case Complexity Rivisted

I got confused with the analysis of algorithms in average case. Following is the my perception regarding average case using sorting problem: Suppose we have a 5 elements array to be sorted using ...
1answer
803 views

### What is the average-case complexity of trial division?

The trial division algorithm for checking if a number $N$ is prime works by trying to divide $N$ by all integers in the range 2, 3, ..., $\lfloor \sqrt{n} \rfloor$. If any of them cleanly divide $N$, ...
0answers
182 views

### Average redundancy in Huffman or Hu-Tucker codes on random symbol probabilities

Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, ...
1answer
68 views

### How is this algorithm average case derived?

For a simple linear search on an unsorted list my textbook says the following: To determine the average case, you add the number of iterations required to find the target at each possible position ...
3answers
601 views

### What is the time complexity of this atrocious algorithm?

This grew out of a discussion of deliberately bad algorithms; credit to benneh on the xkcd forums for the pseudocode algorithm, which I've translated to Python so you can actually run it: ...
2answers
2k views

### What is the average time complexity, for a single linked list, for performing an insert?

I thought this would be a very simple O(n) b.c. you can do the insert any where with in the list. The longer the list, the longer it will take on average to do the ...
2answers
101 views

### Average-case analysis help

I am stuck on trying to understand how to solve the following question. Could someone please explain for a beginner to average-case analysis? Considering the following algorithm A which takes as ...
3answers
6k views

### Average depth of a Binary Search Tree and AVL Tree

My professor recently mentioned that the average depth of the nodes in a binary search tree will be $O(log(n))$ where $n$ is the amount of nodes in the tree. I ended up drawing out a bunch of binary ...
3answers
184 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: ...
1answer
2k 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 ...
0answers
51 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 ...
1answer
1k 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 ...
1answer
192 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 ...
0answers
358 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 ...
1answer
109 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 ...
1answer
22k 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 ...
1answer
85 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 ...
1answer
3k 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 ...
1answer
53 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, ...
4answers
1k 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 ...
1answer
612 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 ...
1answer
517 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 ...
1answer
363 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 case,...
2answers
167 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 never ...
1answer
1k 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 ...