Yeah but there's a formal term for average time complexity, Theta
Θ does not usually mean average, but simultaneously upper and lower asymptotic bounds.
you might want to read that chapter of CLRS again
alt Hacker News
Θ does not usually mean average, but simultaneously upper and lower asymptotic bounds.