10

I think most text book will provide you a good proof. For me, I can show the average case complexity as follows. Assuming a uniform distribution of the position of the value that one wants to find in an array of size $n$. For the case of 1 read, the position should be in the middle so there is a probability of $\frac{1}{n}$ for this case For the case of 2 ...


9

Let $X_{d,t}$ denote the expected number of nodes at level $d$ and time $t$, and let $p_{d,t}$ be the probability that at time $t$, a node is added at level $d$. Our indexing is such that $p_{0,0} = X_{0,t} = 1$. Clearly $$ X_{d,t} = \sum_{s=0}^t p_{d,t}. $$ Suppose that at time $t-1$, the number of leaves at depth $d-1$ is $X$. Then the probability that at ...


8

We can write a recurrence relation for this procedure as follows. Let $T(n)$ be the worst-case time for running sort on a list of length $n$. When calling sort on a list of length $n$, we can have up to $n$ recursive calls which rotate the list to the left until its minimum reaches the first entry. Each such call involves an invocation of minimum, and so ...


8

Worst case, if the second call to rand() returns 0 and the first call doesn't, you get a floating point division by zero, and if you are using standard IEEE 754 arithmetic, the result is +infinity. In that case, the loop will run forever. If you changed your code to exclude that case, and exclude the case that rand () might return a 128 bit integer, then ...


7

There are two notions of expected running time here. Given a randomized algorithm, its running time depends on the random coin tosses. The expected running time is the expectation of the running time with respect to the coin tosses. This quantity depends on the input. For example, quicksort with a random pivot has expected running time $\Theta(n\log n)$. ...


7

Either if you want to insert at the end of the list or at the beginning of the list, you're going to have $O(1)$ Complexity for that and $O(1)$ space. If you want to insert at the beginning of the list, you just make the new list head the node you want to insert, and link it to the previous list head. If you want to insert at the end of the list, you can ...


7

By the prime number theorem, about a $1/\log(n)$ fraction of numbers in the range $[n/2,n]$ are prime. We know that the algorithm will take $\Theta(\sqrt{n})$ time for each of them (since for all $x \in [n/2,n]$, we have $x = \Theta(\sqrt{n})$). Therefore, $$\mathbb{E}[T(X_n)] = \Omega\left({\sqrt{n} \over \log n}\right).$$ This is enough to establish ...


6

This answer refers to a version of the question in which $x$ is sampled by dividing two random numbers. As mentioned by Rick Decker's answer, given $x$, we can approximate the running time by $O(\max(\log x,1))$. Assuming that rand returns a random number in $[0,1]$, the running time should be proportional (up to an additive constant) to $$ \int_0^1 \int_0^...


5

If the value of the $i$-th element is $x$, it causes a heapify, if and only if $j < K$ of the previous $i-1$ elements are smaller than $x$. This gives $$E[X_i] = \frac{1}{N^i} \sum_{x=1}^N \sum_{j=0}^{K-1} c_{j,x},$$ where $c_{j,x}$ is the number of sequences of $i-1$ elements, of which exactly $j$ are smaller than $x$. Now, to determine $c_{j,x}$, ...


5

First assume input is uniformly distributed. More precisely it is $\frac{n+1}{2}$. When you search for a particular element $x$ in an array of size $n$, that element may be located at the position either $1$, or $2$, $\dots$ or $n$. When we search we check each element in the array and compare it with $x$, and so when we reach $k^\text{th}$ element of the ...


4

Hard on average is sometimes defined as in your third (simple) definition: a function $h$ is hard on average if on a uniformly random input, its output cannot be predicted by a ppt with more than a negligible probability. The first definition also captures the situation in which the "correct" input distribution is different. For example, consider the ...


4

You can't, not really, for three reasons: Number of operations and runtime do not compare well; too many factors (typically) left out in analysis influence actual runtime. Asymptotic results (which hold in the limit) and a finite sets of observations do not compare. Landau classes don't compare with "exact" functions. For instance, if you have $f \in O(n^3)$...


4

Since you don't do any reordering while splitting, the length of array after the while loop can not be larger than the length of the longest increasing subsequence in the input. Since that one is on average about $2\sqrt{n}$ elements long¹, you keep too many elements in unsorted. In particular, there is no $b$ so that your ansatz describes the actual ...


4

If you have no additional requirements on the contents of the list, you can just insert the item at the head, which is O(1). If you do (e.g. the list must be kept sorted or deduplicated), insertion is more expensive.


4

Don Knuth recently gave a recreation of his first lecture ever given at Stanford in which he addresses precisely this question with virtually the same code structure as what you have above. True to form, he showed up with a wig and authentic 1960's attire. You can watch a recording of that lecture online if you're interested. Another way to derive this ...


4

The average case running time of quicksort satisfies the recurrence $$ T(n) = \frac{1}{n} \sum_{i=1}^n [T(i-1) + T(n-i)] + \Theta(n), $$ with base case $T(0) = \Theta(1)$. In view of solving this recurrence, let us replace $\Theta(n)$ with $n+1$ and $\Theta(1)$ with $2$ (the reason for these specific choices will become apparent below). Changing the order ...


3

The two are not mutually exclusive. In most situations you're interested in amortized analysis, since usually operations are fast enough so that no user would notice a one time long running time, the real performance being determined by the amortized running time. A good example is garbage collection, essential to many modern computer languages. Garbage ...


3

Your question refers to average depth of the nodes in a BST, but it's easiest answer this by thinking about the overall height of the tree first. In the worst case, the depth of the tree can be $n$, assuming it's not a balanced tree and the inputs are sorted, so the resultant tree ends up being a very deep linked list. In that case, the average depth of ...


3

If you don't have any degree-1 nodes in your trie (which is a tree) than you have more leaves than interior nodes. So in this case you have $I\le n $. It depends a bit how you define the trie whether you can have many interior degree-1 nodes. If you study a compressed trie the all the path of degree-1 nodes are merges to an edge, so you are done. For an ...


3

Here is a similar recent example due to Mossel et al. There are $n$ vertices which are partitioned randomly into two classes. Two vertices of the same type are connected with probability $p$, and two of opposite types with probability $q$. For what values of $p, q$ can we recover the partition with high probability (with respect to $n$)? It turns out that if ...


3

As I pointed out in the comments, the primary feature of interest for understanding how a genetic algorithm (or evolution, even) explores the fitness landscape is the fitness function. In this case, you specified an extremely simple fitness function with no epistasis. This was a standard assumption for analytical tractability when biology first started out (...


3

I'll just answer a) and b) because I don't know the potential method. About a) Worst case analysis only considers a single operation. If you want to know how expensive your algorithm is in its worst case, you need to find the worst case cost of every single operation and then count how often each of them is executed. For example, you may have come about a ...


3

In short, the average is the expected value of the uniform distribution. If $T(x)$ denotes the runtime of some algorithm on input $x \in \mathcal{X}$, then the expected runtime for input size $n$ is $\qquad\displaystyle \mathbb{E}[T(X) \mid |X| = n] = \sum_{x\in\mathcal{X}_n} \operatorname{Pr}[X=x \mid |X| = n] \cdot T(x)$ given some random distribution ...


3

In chained hash tables with uniform hashing a similar question arises. Given a table with $n$ elements hashed into $m$ buckets, the expected number of elements per bucket is $n/m$, but what is the expected length of the longest chain? I found a Stackoverflow question about chained hash tables. The answer by btilly argues that for fixed ratio $n/m$ the ...


3

The sum $n+(n-1)+\dots + 3+2+1$ evaluates to $n(n+1)/2$ (it's the so-called Gauss sum). Now divide by $n$, you and get $(n+1)/2$.


3

There are two prominent uses of the term "average" in algorithm analysis. Average-case as a special case of expected costs Here, "average case" just means "expected case w.r.t. uniform distribution". Since we usually analyse with uniform inputs in mind (everything else is hard, and there's not much reason to prefer one distribution over the other in most ...


3

The number of times that max is assigned to is known as the number of records (or left-to-right maxima) in the permutation. The following results are standard, and can be found in a paper of Kortchemski, which gives a much more refined analysis. Lemma 1. Let $X_1,\ldots,X_n$ be indicator variables for the events that the $i$th element of a random ...


3

Instead of giving an answer, I will try to paraphrase the steps, I hope this will help you solve your homework. Identify the problem: What is the input? What is the output? Comprehend the problem: Can you write a formula for the problem, that relates input to the output? What is the formula for the average of x numbers? Identify different alternatives to ...


3

It's neither ${(n^2+3n)}/{(2n+2)}$ nor $n/2$. In fact, the question itself doesn't make much sense at all. In order to be able to talk about the average running time of an algorithm, you have to fix a probability distribution for the input. As an example, it is well known that the average running time of naive quicksort is $\Theta(n \log n)$, but that result ...


Only top voted, non community-wiki answers of a minimum length are eligible