New answers tagged

2

Let us replace $\Theta(n)$ with $n$, for concreteness, and assume a base case of $T(0) = 0$. Let's try to prove inductively that $T(n) \geq cf(n)$, where $f(n) = n\log n$ for all $n$ (where $0\log 0 = 0$). During the proof, we will need to minimize $f(q) + f(m-q)$ for $0 \leq q \leq m$. Since $f'(n) = \log n + 1$, any minimum point must satisfy $$ \log q + ...


1

You can use the recursion tree method. The amount of work on the level at depth $0$ is at least $c n$ for some constant $c$ (from the $\Theta(\cdot)$ notation). The amount of work at depth $1$ is at least $c q + c (n-q -1) = c(n-1)$. The amount of work on the next level is at least $c(n-3)$ and, in general, the total amount of work on the level at depth $d$ ...


1

If $p \leq k \leq i$ then $A[k] \leq x.$ In the algorithm when for example, $p$ is $1$, won't $i$ be $0$.... How would this hold, since before the for loop we have i = p-1 Although, as you have observed, $i$ is always smaller than $p$ at the start of the loop, it might become bigger because the statement "$i=i+1$" in the loop could be executed. Once $i$ ...


0

I'm not in the mood of tracing a code rightnow, but understand that u start with A[r] =X and ends with A[i] =X (the pivot, which seems to be chosen as the last element $r$ in the given code, reaches its correct position with the rest of the list get paritioned) -At a first glance maybe the code has some errors, there is no need for the exchange in the ...


Top 50 recent answers are included