# Tag Info

22

Let's first think about this intuitively. In the best-case scenario, the tree is perfectly balanced; in the worst-case scenario, the tree is entirely unbalanced: Starting from the root node $p$, this left tree has twice as many nodes at each succeeding depth, such that the tree has $n=\sum_{i=0}^{h}2^i =2^{h+1}-1$ nodes and a height $h$ (which is in this ...

12

Let $\sf{Bubble Sort}$ be defined as the following: for (j = A.length; j > 1; j--) for (i = 0; i < j - 1; i++) if (A[i] > A[i + 1]) swap(i, i + 1, A) Given some permutation $x_1, \cdots, x_n$, an inversion is said to have occurred if $x_j < x_i$ for some $i < j.$ We see that $\sf{Bubble Sort}$ performs an inversion ...

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 ...

9

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 ...

8

Recall, how expected value is defined. You count the for every element $X$ in the tree the number of comparisons it takes to locate it, say $C(X)$. Then $$E[\text{# of comparisons}]=\sum_{X\in\{A,\ldots,H\}} p_X \cdot C(X),$$ where $p_x$ denotes the probability that $X$ is chosen, which is the same for all $X$, namely $1/8$. In other words, you compute the ...

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

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

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 ...

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 Here's an elaboration of The Unfun Cat's answer. For convenience, let the numbers be v_1,\ldots,v_n. Whatever the value of v_1 is, for i>1 we have \Pr[v_i = 10-v_1] = 1/9. Therefore, the number of iterations of the second loop is roughly distributed geometrically G(1/9), so we expect it to run about 9 times. A complication is that n is not ... 5 Let us assume that required element is equally likely to be in any position between 1 and n. Let x _i  be a random variable. Random variable x_i = 1 means required element is in ith position and vice-versa. Now probability that required element is in position between 1 and n is$$ Pr[x_i = 1] = \frac{1}{n}$$Now Expected value is given by$$\...

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

An insight here is that the probability of returning early does not depend on the length of the input (as long as numbers.length is of such a size that you would expect to find two numbers that add to ten). You need to compute the probability $p$ that two integers between one and nine add to ten. Then solve $p*x=1$ and $x$ is the number of iterations done ...

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

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)$. ...

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

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

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

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

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

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

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

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 ...

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