search
Log In
0 votes
59 views
Show that the expression $q^2 +(n-q-1)^2$ achieves a maximum over $q=0,1,\dots ,n-1$ when $q=0$ or $q=n-1$.
in Algorithms 59 views

1 Answer

0 votes

this might help.

Related questions

0 votes
1 answer
1
0 votes
2 answers
2
0 votes
1 answer
3
183 views
Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst a $\alpha$-to-$(1-\alpha)$ split, as a function of $\alpha$ in the range $0<\alpha<1$.
asked Jun 28, 2019 in Algorithms akash.dinkar12 183 views
0 votes
1 answer
4
76 views
We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is nearly sorted. Upon calling quicksort on a subarray with fewer than $k$ elements, let it simply return without sorting the subarray. After the top-level ... runs in $O(nk+n\ lg\ (n/k))$ expected time. How should we pick $k$, both in theory and in practice?
asked Jun 28, 2019 in Algorithms akash.dinkar12 76 views
...