Analysing time complexity
Try to find an explicit formula for $T(n)$: Start by writing a few examples, such as $T(2)$, $T(4)$, etc.
Then, after you got some intuition on how $T(n)$ behaves, formulate it as a summation, and find a closed form for it. I will give the example of how to do it for the &quot;best case&quot; scenario:
Examples
$T(2) = T(1) + c_1 \cdot 2$
$T(4) = T(2) + c_1 \cdot 4 = T(1) + c_1 \cdot 4 + c_1 \cdot 2 = T(1) + c_1 \cdot (4 + 2)$
$T(8) = T(4) + c_1 \cdot 8 = T(1) + c_1 \cdot 8 + c_1 \cdot 4 + c_1 \cdot 2 = T(1) + c_1 \cdot (8+4+2)$
Opening recursion
And now (try for yourself) you can prove using induction that:
$T(n) = T(1) + c_1 \sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{n}{2^k}$
Finding closed form
Notice that $\sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{1}{2^k} = \frac{\left(\frac{1}{2}\right)^{\lfloor \log(n) \rfloor} - 1}{\frac{1}{2}-1} = \frac{1 - \frac{1}{n}}{\frac{1}{2}} \le 2$ Since it is the sum of a geometric progression.
Therefore, $T(n) = T(1) + c_1 \cdot n \cdot \sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{1}{2^k} \le T(1) + c_1 \cdot 2 \cdot n = O(n)$