On: Python sets and dictionaries can have quadratic-time performance

[jpitz]

Yeah but there's a formal term for average time complexity, Theta

[emil-lp → jpitz]

Θ does not usually mean average, but simultaneously upper and lower asymptotic bounds.

[xdavidliu → jpitz]

you might want to read that chapter of CLRS again

[jpitz → xdavidliu]

You're right.

It isn't the average bound, it is the upper and lower bound stated together ( as long as thats the same function )