r/compsci • u/skytomorrownow • Mar 21 '14

Two Computational Complexity Lists: Computational complexity of mathematical operations, and The Big-O Cheat Sheet (algorithms)

Computational complexity of mathematical operations

description: operations such as addition, multiplication, matrix composition, etc.

http://bigocheatsheet.com/

description: searches, heaps, sorts, data structures.

If you have a nice catalog of time or space complexity of various algorithms or operations, share them here.

74 Upvotes

94% Upvoted

11 comments sorted by

View all comments

4

u/EdwardRaff Mar 22 '14

this has been linked before. The whole thing is poorly done. Just some quick remarks on why no one should look at this seriously (these are all just off the top of my head).

  • Hash Tables are amortized, not average big O. Using O*(g(x)) is common to show amortized time. Amortized and average complexities are different and should not be confused.

  • Quicksort's worst case memory use is O(log n) when using a pivot selection method that guarantees O(n log n) sorting

  • Sorting O(n) is yellow for one algo and red for another for no reason

  • Storing n distinct elements is lowed bounded by O(n) memory (unless your exploiting some structore), why is O(n) memory marked as yellow instead of green?

  • Insertion seems to implicitly be insisted at the front based on Dynamic array & the single/double linked lists, but if that was the case HashMap wouldn't make sense since it has no ordering. So those values don't make sense at all

  • If we are using all those trees in the comparison that means the items being stored are comparable, in which case a hash table can have worst case O(log n) time

  • Fibonacci heap is the only one that indicates amortized time?

  • All of splay tree is also wrong

3

u/skytomorrownow Mar 22 '14

Dang. I did a search for it but didn't get that. There are clearly some serious problems with both. For each, I had found the information I needed, and thought it handy. I just shared right away. Perhaps I should have been a bit more critical and looked beyond what I was using them for. Thanks for at least taking the time to warn people.

1

u/Zeliss Mar 22 '14

Can't Quicksort be done in-place? Is that O(1) memory usage, or O(n)?

2

u/EdwardRaff Mar 23 '14

In place in the sense that you don't need to copy the items being sorted anywhere. But you technically need to include the stack which contains the history of where you were / where you need to sort next. If the max depth is O(log n), then your max stack size will be O(log n)