Skip to main content

Questions tagged [average-case]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers
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 ...
Saad Ahmed's user avatar
-1 votes
1 answer
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: ...
user_1234's user avatar
1 vote
0 answers
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....
lmonninger's user avatar
1 vote
1 answer
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 ...
Colonizor48's user avatar
1 vote
1 answer
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 ...
User315150's user avatar
1 vote
0 answers
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 ...
user777's user avatar
  • 749
1 vote
1 answer
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 ...
grozby's user avatar
  • 21
1 vote
1 answer
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)$, ...
Ben I.'s user avatar
  • 1,710
1 vote
0 answers
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 ...
Emad's user avatar
  • 411
3 votes
0 answers
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 ...
Request Savitch's user avatar
4 votes
3 answers
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. ...
chausies's user avatar
  • 532
0 votes
1 answer
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 ...
scand1sk's user avatar
  • 125
0 votes
1 answer
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: ...
AceVenturos's user avatar
5 votes
0 answers
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 ...
hello_moto's user avatar
2 votes
2 answers
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. ...
Hex's user avatar
  • 23
1 vote
1 answer
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{?} $$
user avatar
3 votes
1 answer
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 ...
Abhishek Ghosh's user avatar
2 votes
1 answer
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 ? ...
alyssaeliyah's user avatar
5 votes
4 answers
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 ...
wlad's user avatar
  • 489
1 vote
0 answers
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 ...
firejox's user avatar
  • 11
2 votes
2 answers
297 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(...
zbh2047's user avatar
  • 296
3 votes
1 answer
2k 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 ...
M. Twain's user avatar
2 votes
1 answer
2k 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 ...
A.R.S's user avatar
  • 73
2 votes
1 answer
276 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%...
1419636215's user avatar
2 votes
1 answer
868 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], \...
hengxin's user avatar
  • 9,561
0 votes
1 answer
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 ...
user1620122's user avatar
1 vote
1 answer
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. ...
Paradox's user avatar
  • 320
0 votes
1 answer
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. ...
Shial De's user avatar
1 vote
1 answer
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, ...
Genxers's user avatar
  • 13
4 votes
1 answer
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 ...
Max Koretskyi's user avatar
2 votes
1 answer
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 ...
ElleryL's user avatar
  • 171
2 votes
3 answers
3k views

Time complexity of this while loop

So, i would like to know the time complexity of the following codes: ...
erwinleonardy's user avatar
0 votes
1 answer
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 ...
Amir Qasemi's user avatar
0 votes
0 answers
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 ...
soka's user avatar
  • 11
3 votes
3 answers
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) ...
hengxin's user avatar
  • 9,561
3 votes
3 answers
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. ...
Yiyuan Lee's user avatar
0 votes
1 answer
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 ...
Joe's user avatar
  • 3
0 votes
0 answers
344 views

Partition algorithm average-case complexity analysis

I was given the following algorithm: ...
fuw's user avatar
  • 1
1 vote
1 answer
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 ...
PKG's user avatar
  • 1,489
1 vote
3 answers
2k views

Average-Case Analysis of a Simple Max-Finding Algorithm

Given this piece of code: ...
xavier's user avatar
  • 11
1 vote
2 answers
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 ...
Charlie Parker's user avatar
2 votes
2 answers
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 ...
Seeker's user avatar
  • 389
9 votes
1 answer
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$, ...
templatetypedef's user avatar
5 votes
0 answers
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, ...
Sebastian's user avatar
  • 4,536
-1 votes
1 answer
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 ...
flybonzai's user avatar
  • 109
6 votes
3 answers
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: ...
Wildcard's user avatar
  • 335
4 votes
3 answers
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 ...
cade galt's user avatar
  • 141
2 votes
2 answers
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 ...
roro172's user avatar
  • 21
6 votes
3 answers
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 ...
Nickknack's user avatar
  • 213
5 votes
3 answers
227 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: ...
Mets's user avatar
  • 53