While solving the recurrence $$T(n) \leq (n-1) +\frac{2}{n} \sum_{i= n/2}^{n-1} T(i)$$ our professor directly went to the hypothesis step without showing the basis step. Here the hypothesis step is:
Assume inductively that $T(i) \leq 4i$ for $i < n$.
Edit: Here is complete context:
Let $T(n, k)$ denote the expected time to find the $k$-th smallest in an array of size $n$, and let $T(n) = \max_k T(n, k)$. We will show that $T(n) < 4n$.
First of all, it takes $n-1$ comparisons to split into the array into two pieces in Step 2. These pieces are equally likely to have size $0$ and $n-1$, or $1$ and $n-2$, or $2$ and $n-3$, and so on up to $n-1$ and $0$. The piece we recurse on will depend on $k$, but since we are only giving an upper bound, we can imagine that we always recurse on the larger piece.
What would be appropriate basis step for this recurrence ?
Thanks in advance.
$$T(i)\le4i\text{ for }i<n,$$ for some $n$ which depends on the problem on hand (I cannot guess).
E.g. $$T(1)\le4,T(2)\le8.$$