[bvinc]

My understanding is that automatically determining time complexity is impossible in the general case due to the halting problem.

And getting a compiler to truly understand the time complexities of your data structures would involve either extremely difficult theorem proving or just forcing it.

I do think it would still be interesting if a language had support for determining time complexity. It seems like it's often possible even if it isn't in the general case.

[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.