Questions tagged [average-case]
The average-case tag has no summary.
80 questions
2 votes
1 answer
131 views
Does O(1) average-case imply O(1) generic-case?
We have an algorithm that has an average time complexity of $O(1)$. We wanted to analyse the generic time complexity of the same algorithm. Our coäuthor claimed that $O(1)$ average-case implies $O(1)$ ...
2 votes
0 answers
58 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 ...
- 21
-1 votes
1 answer
181 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: ...
- 99
1 vote
0 answers
82 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
1 answer
80 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 ...
- 239
1 vote
1 answer
73 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 ...
- 11
1 vote
0 answers
59 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 ...
- 759
1 vote
1 answer
266 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
1 answer
299 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,730
1 vote
0 answers
46 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 ...
- 431
3 votes
0 answers
145 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 ...
4 votes
3 answers
345 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. ...
- 652
0 votes
1 answer
991 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
1 vote
1 answer
298 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: ...
- 11
5 votes
0 answers
704 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 ...
- 59