Should most entries have no Theta() time complexity set listed?

ericdrowell / BigOCheatSheet

1.07k stars 312 forks source link

Should most entries have no Theta() time complexity set listed? #128

Open D-Zimarev opened 6 years ago

D-Zimarev commented 6 years ago

In set terms Theta() is the intersection of O() and Omega() [more info at the highest ranked answer in this complexity question on stackoverflow].
Very few algorithms have Theta() (merge sort being one of the few examples), however all algorithms in the cheatsheet seem to have entries).
There also seems to be mixing between best, average, worst and the mathematical concepts of big Omega, Theta, O.

glebec commented 6 years ago

Just saw that the cheat sheet has conflated the ideas of best/average/worst input case vs Big Omega / Theta / O. I’m disappointed, these are NOT the same concepts at all. The sheet as it stands is incorrect.

Related to #124

umanwizard commented 5 years ago

Very few algorithms have Theta()

This is still a misunderstanding. You are still confusing big-Theta and big-O with average vs. worst case. Big-whatever has nothing to do with probability! Quicksort for example is Theta(n * log(n)) average case, Theta(n^2) worst case.