Questions tagged [average-case]

The tag has no usage guidance.

79 questions
Filter by
Sorted by
Tagged with
33 views

On a set of points uniformly distributed in a circle, on average, what would be better? Graham's scan or Jarvis's march

I got this question in an exam and my approach was to use probability. Jarvis's march is better than Graham's scan if h < log(n) So I calculated the probability of a point being on the circle ...
107 views

How to calculate average hours worked from bar graph

I want to calculate average hours worked from below bar graph and following this method but I feel this method is not correct to find average working hours Procedure A: ...
1 vote
56 views

Find the smallest Valeriepieris circle

The Valeriepieris Circle is a circle within which it is supposed that the majority of the World's population lives. I'm interested in general-case and average-case algorithms for finding such a circle....
• 133
1 vote
44 views

Are there arbitraraly hard worst case problems with polynomial time average case complexity?

For example, are there worst case Decidable(but non primitive recursive or other insane time complexity)problems that have a polynomial average case complexity? If so Are there undecidable worst case ...
• 229
1 vote
33 views

Average-case complexity for coNP

I have been unable to find any literature on average-case complexity for coNP, other than a folklore conjecture that most tautologies are hard for any given propositional proof systems and some ...
1 vote
42 views

A minor issue on the proof of "if (L',D') is easy, then so is (L,D)" in Average-case Complexity!

In Arora and Barak's textbook, in chapter 18, p.366-367, they prove the following theorem: Theorem 18.7 if $(L,D)$ is reduced to $(L',D')$ and $(L',D') \in disP$, then $(L,D) \in disP$ The proof ...
• 749
1 vote
156 views

Amortized analysis (accounting/banker's method) for tree operations

Suppose we have a tree data structure with root $r$ with two operations: Add($x, y$) - adds the node $y$ as a child to the node $x$ Zip($x$)- this makes the node $x$ and all of $x$'s ancenstors direct ...
• 21
1 vote
230 views

Average case complexity and Big-O

In this Wikipedia article on Average-case complexity there is the text: For example, many sorting algorithms which utilize randomness, such as Quicksort, have a worst-case running time of $O(n^2)$, ...
• 1,710
1 vote
36 views

Average-case retrieval time

The book CLRS claims these statements before introducing the topic of universal hashing: If a malicious adversary chooses the keys to be hashed by some fixed hash function, then the adversary can ...
• 411
106 views

Running time analysis of Savitch's algorithm

Savitch provided an algorithm which places NL in L^2 and hence the runtime of the algorithm is bound by $2^{O(\log^2n)}$. The runtime of the algorithm is not in P as NL is not known to be in SC. Is ...
233 views

What is a sorting algorithm that is robust to a faulty comparison?

I want to sort a list of n items with a comparison sort. However, one of the comparisons made by the algorithm will be flipped from what it's supposed to be. ...
• 532
772 views

Average time complexity of linear search

It is usually assumed that the average time complexity of the linear search, i.e., deciding whether an item $i$ is present in an unordered list $L$ of length $n$ is $O(n)$ (linear). I have read ...
• 125
244 views

Average case analysis by key comparisons of Max Sort

I'm having trouble approaching this average case analysis in terms of key comparisons. The pseudo-code is as follows: ...
604 views

How to find the Expected height of a randomly built binary tree

I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
581 views

Trouble finding average case of a find max algorithm

I'm trying to find the average case number of times that max is assigned by the algorithm findMax included below. ...
• 23
1 vote
48 views

Asymptotic growth of a series

How we can prove that: $$\sum_{k=1}^{c \log n-1}\:k\cdot \left(\frac{1}{2}\right)^{\frac{k}{3}}\in O\left(1\right) \quad \mbox{?}$$
432 views

Average Case Analysis of Insertion Sort as dealt in Kenneth Rosen's "Discrete Mathemathematics and its Application"

I was going through "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the following algorithm of the Insertion Sort and also its analysis. The algorithm is quite ...
• 1,142
567 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 ? ...
• 205
2k 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 ...
• 489
1 vote
102 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 ...
• 11
297 views

• 9,561
239 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 ...
• 123
1 vote
1k 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. ...
• 320
143 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
588 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, ...
• 13
15k 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 ...
134 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 ...
• 171
3k views

Time complexity of this while loop

So, i would like to know the time complexity of the following codes: ...
328 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 ...
22 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 ...
• 11
411 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) ...
• 9,561
3k 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. ...
• 155
453 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 ...
• 3
344 views

Partition algorithm average-case complexity analysis

I was given the following algorithm: ...
• 1
1 vote
144 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,489
1 vote
2k views

Average-Case Analysis of a Simple Max-Finding Algorithm

Given this piece of code: ...
• 11
1 vote
435 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,050
643 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 ...
• 389
2k 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$, ...
• 9,142
268 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, ...
• 4,536
84 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 ...
• 109
720 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: ...
• 335
26k 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 ...
• 141
166 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 ...
• 21
16k 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 ...
• 213
A comparison sort cannot require fewer than $\Theta (n\log n)$ comparisons on average. However, consider this sorting algorithm: ...