CODEWITHSUNDEEP
algorithmdata-structuresbig-o
Leonardo Lopez
Leonardo Lopez

Reputation: 1143

When someone talks about the Big-O of an algorithm without qualification, are they referring to the best, the average, or the worst running case?

When someone talks about the Big-O of an algorithm without qualification, are they referring to the best, the average, or the worst running case? Key word is 'without qualification'.

Upvotes: 1

Views: 77

Answers (1)

James Oravec
James Oravec

Reputation: 20381

Big-O technically is the upper bound, so you want worst case analysis.

There are also Big-Omega and Big-Theta, as well as expected case (if using randomization), average, etc. Normally if someone doesn't specify, you can do just the Big-O, however if you are easily able to provide more info, then you might as well. e.g. Big-Theta gives you the Big-O and additional information. If you are taking an algorithms class and need to provide an analysis of problems, then you'll want to talk with your professor to see what they expect. More than likely, they are looking to see how much you can figure out, so without qualification might mean show them what you know or can figure out.

When in doubt, as the person who is asking for the information for further clarification. Normally the more information you can figure out, the better. You might find strengths of algorithms by doing further analysis.

For example, using a linked list is great for insertion O(1). As long as you don't need to search for anything then it might be a desirable data structure to use in an algorithm. If your algorithm needs to do lots of searching, then a linked list is probably not the data structure to use with you algorithm.

Upvotes: 1

Related Questions