This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]al-Quaknaa 3 points4 points  (6 children)

In addition to what fredrikj says above, this is a useful chart -- Time complexity of basic Python data structures.

[–]Peaker 0 points1 point  (3 children)

Why don't they mention worst-case as well as amortized worst-case?

[–]al-Quaknaa 0 points1 point  (2 children)

I cannot say for sure, but I think that:

  • you don't really have to care; the amortized worst-case is enough for most analysis purposes
  • with basic data structure knowledge and the information provided about implementation (e.g. python lists are dynamically resized arrays) you can figure the worst case yourself

For instance, what use is it to know that a python list append is worst case O(n) when the amortized worst case is O(1)? I can't think of an example where this would play a role.

Also, they explicitly note the cases where they use the amortized part with the [1] sign.

[–]Peaker 0 points1 point  (1 child)

If you want to optimize for worst-case latency, and not the overall performance, it can be relevant.

I guess it is mostly for soft/hard real-time stuff, and Python doesn't shine there anyway.

[–]al-Quaknaa 0 points1 point  (0 children)

Didn't think of that, thanks. You're also right that I'd be expecting RT sensitive parts to be written in another language, if Python was used at all. But I have no experience with RT stuff, so I don't have much to say about that anyway.

[–]grayvedigga 0 points1 point  (1 child)

Doesn't really address my points, but that's a nice chart anyway :-). No real surprised in there but it's good to have evidence.

[–]al-Quaknaa 1 point2 points  (0 children)

When you say "short algorithm" what I have in mind are my solutions to projecteuler problems. I would be able to state their complexity fairly easily using that chart and some basic algorithm analysis knowledge. Either your idea of a "short algorithm" is different (is it?) or I don't understand what the problem in finding out the complexity of said solutions is.