According to various informal analysis, we know that the running time of quickselect is o(n), by assuming thay the partition is always taking half of the array. However, my lecture gives without proof that if we do a formal analysis, we will get the following formula:
$$C_N = 2 N + 2 k ln (N / k) + 2 (N – k) ln (N / (N – k))$$
*$C_n$ is the number of compares if the array has N items.
Does anyone know how this formula is derived?