[Quekid5]

Another issue is that algorithmic complexity only really 'composes' in a trivial and uninteresting way: Ok, you have a for loop over N items, multiply the complexity of the loop body by N.

Well, no not quite... it may be the case that one particular iteration of the loop makes all the subsequent steps completely trivial, so O(1)... and even further it may be that such a step is guaranteed to be reached in log(M) time, etc. etc. You see this type of thing a log in graph algorithms where they look like they might be O(n^3) or whatever, but leaving markers on nodes can avoid a lot of repeated work (by skipping marked node), so they end up as O(n + k) or whatever.

Upper bounds for worst case complexity are relatively easy... just assume the worst, but the interesting thing is proving TIGHT bounds for worst case complexity.