quicksort - Why is $\log_4 n$ used as an approximation instead of $\log_2 n$? Below is an excerpt from Khan Academy's Quick Sort Analysis page. 



In the average case of quicksort they assume that each time the partition function breaks the input array into the ratio 1:3 each time.

So why is it easier to assume $\log_4 n$ levels when the $n$ elements are being partitioned ? Why not assume it to be $\log_2 n$ levels ? 

Wouldn't $\log_4 n$ and $\log_2 n$ mean the same thing here ?
No, $\log_4 n$ is not the same as $\log_2 n$. $\log_4$ is exactly $\frac{\log_2 n}{2}$. At the end of the complexity computation you can obviously say that $O(\log_4 n) = O(\log_2 n)$. But at this point they aren't computing the complexity (yet). They are doing "exact" math. If you have an array with $n$ elements and you always divide it by $4$, it will take exactly $\lceil\log_4 n \rceil$ iterations until you reach the size $1$, and not $\lceil \log_2 n \rceil$. 

One more thing. They don't proof, that the average runtime is $\Theta(n \lg n)$. Because the array will obviously not always split with a ratio of 1:3. They only give you some intuition, why the complexity makes sence. Like they mention in the article:


  Showing that the average-case running time is also $\Theta(n \lg n)$ 
  takes some pretty involved mathematics, and so we won't
  go there.