Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [average-case]

The tag has no usage guidance.

1
vote
2answers
81 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 ...
1
vote
0answers
45 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 ...
2
votes
1answer
66 views

How to estimate the average time complexity of greatest common divisor?

As we know, the time complexity of $\gcd(x,y)$ is $O(\log \min(x,y))$ by using Euclidean algorithm. Now we fix a constant $n$ and consider the average time complexity of $\gcd(x,n)$. Formally, let $f(...
3
votes
1answer
304 views

Average-case complexity of linear search where half of the elements in the array are duplicates

I know that for an array of size n distinct elements, the Average Case complexity for linear search is as follows: A(n) = $\frac{n + 1}{2}$ However, I am having trouble coming up with the Average ...
2
votes
1answer
349 views

Average case of simple algorithm like binary search

These questions is about one of my research. As I am not a computer scientist, formal answering is difficult to me. I have a special search algorithm which the explanation here will take a lot of ...
2
votes
1answer
144 views

Weighted probability using Huffman Tree

I want to produce a value from a set, where each value has an associated weight. Eg: [(1, 4), (2, 3), (3, 3)] should give me a 40% chance of picking 1, and a 30%...
2
votes
1answer
128 views

Average-case analysis of linear search given that the desired element appears $k$ times

The problem below is adapted from CLRS Problem 5-2 "Searching an unsorted array": Consider a deterministic linear search algorithm which searches an array $A$ for $x$ in order, say $A[1], A[2], \...
0
votes
1answer
111 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 ...
0
votes
1answer
266 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. ...
0
votes
2answers
87 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. ...
1
vote
1answer
304 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, ...
3
votes
1answer
5k 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 ...
2
votes
1answer
59 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 ...
2
votes
3answers
2k views

Time complexity of this while loop

So, i would like to know the time complexity of the following codes: ...
0
votes
1answer
201 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 ...
0
votes
0answers
20 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 ...
2
votes
3answers
150 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) ...
4
votes
2answers
796 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. ...
0
votes
1answer
162 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 ...
0
votes
0answers
256 views

Partition algorithm average-case complexity analysis

I was given the following algorithm: ...
0
votes
1answer
51 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 ...
1
vote
2answers
530 views
1
vote
2answers
246 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 ...
3
votes
1answer
390 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 ...
6
votes
1answer
673 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$, ...
5
votes
0answers
169 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, ...
-1
votes
1answer
65 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 ...
6
votes
3answers
578 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: ...
3
votes
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 ...
2
votes
2answers
97 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 ...
6
votes
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 ...
5
votes
3answers
137 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
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 ...
1
vote
0answers
48 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
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 ...
3
votes
1answer
178 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
347 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 ...
3
votes
1answer
105 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 ...
4
votes
1answer
20k 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
84 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
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 ...
2
votes
1answer
52 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, ...
3
votes
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 ...
5
votes
1answer
583 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
502 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
327 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,...
4
votes
2answers
159 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 ...
2
votes
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 ...
0
votes
1answer
80 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 ...
6
votes
2answers
405 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$. Keep ...