9. For the following algorithm: 1). Provide the time and space analysis for best-case and worst-case. 2). Implement a recursive version of it, and provide the time and space analysis for best-case and worst-case for your implementation.

For the following algorithm: public static Comparable select(Comparable[] a, int k) { if (kc0 | | k>=a.length) return null; int lo-O, hi-a.length-1; while (hi > lo) { int j partition(a, lo, hi); return a[k]; else if (j> k) 1; else if (j