Big-O: How do you know what algorithm to give for a specific time complexity?

Question

So when someone asks you to give a O(n) or a O(nlogn) algorithm to compute something, how do you know what to answer? It seems the only way of being able to answer this sort of question is knowing the time complexities of various algorithms beforehand, rather than thinking up something on the spot. Am I correct in assuming this?

Answer 1

simple cases are:

Iteration along the list - O(n)

Single binary or tree operation - O(log n) (which means insertion of n elements into the tree is n log n)

Hashtable operation - O(1)

NP complete problem (here you need some experience to develop an intuition) - exponential time in general (in practice for many problems an efficient heuristics can be applied)

for graph with E edges and V vertices the complexity is F(E,V) depending on the nature of the algorithm and density of the graph. E+V for good DFS/BFS.

Almost every algorithm can be partitioned into the set of above (or similar) small blocks. When blocks are combined recursively, like A-includes-B, the complexity multiplies, when blocks follow each other, like A-then-B, the complexity is max(complexity A, complexity B)

Answer 2

You are right, you should know the time complexities for different algorithms to know this. You should know the time complexities for sorting, for finding items in a dictionary, in a hash table, union find, flow graphs, DFS, BFS, minimum spanning trees, etc. These are the basics.

Introduction to Algorithms should have you well covered.