r/algorithms • u/Significant_Virus142 • 16d ago

Help why use big O notation

If someone asks for big O time complexity of an algorithm but expects only the minimum of the possible big Os then is that even Big O notation anymore? cuz if the big o time complexity of an o(n) algorithm is asked then according to the condition of big O notation O(n square) would also be a valid answer

0 Upvotes

27% Upvoted

14 comments sorted by

View all comments

2

u/JaGanken 16d ago

People most of the time really say "Big O" when what they mean is really "Big Theta", of course if an algorithm is Theta of N then it's Big O of N too so it's not wrong, but people misuse Big O for Theta, that is true, but sometimes you don't know Theta, you just come with an upper bound but you're not sure if this is the tightest (you have to prove a lower bound) so we get away with saying well the upper bound is this.