Many of you use existing libraries such as list, HashMap, unorder map, and announce your code is a O(1) resolution.
- What will you do if the language is standard C which doesn't have these classes to handle the hash,map, link?
- How do you think the 'find' operation in the HashMap/unorder map is O(1) in worst case ? -- so your resolution based on them is also O(1)?
The basic is, you can't use an algorithm implemented in c++ STL or in java package to resolve the algorithm problem.
@Maggie2011 why not? of course you can always go and implement your own data structs like HT or LL but you need to spend a lot of effort to get where STL/CF is.
Worst run-time is often not optimized for because the average is more important in many applications. Often you have a better average if you accept worst case behavior that's not optimal but statistically extremely rare. So, they usually imply O of average case and not O of worst case. Its good to be aware that's not the same, totally agree with you.
btw in some hard real-time scenarios they optimize for worst case and accept worse average case due to the need for a deterministic behavior.