2
$\begingroup$

It seems that the most popular source on the internet on this topic is https://www.bigocheatsheet.com/: enter image description here

Wikipedia and basically any other similar table I find on the internet copy this one.

There are some things that without a brief explanation are very difficult for me to understand or are a bit confusing. For example, as a user mentions here, comparing the access time of BST vs array can be "unfair... since in a BST, 'Access' also gives you the i-th smallest element, whereas in a simple array you get only some element".

I wonder if anyone knows of a good source that concisely explains the differences in complexity of those operations for those structures, without me having to read 14 lengthy wikipedia articles.

On the other hand, there is the problem that now I don't trust that sources either, since with my little knowledge on the subject I have found an error. I mean, Insertion and deletion in Singly-Linked List is not O(1) but O(n).

I would appreciate if someone can give me a hand.

Improve this question
$\endgroup$
2
  • $\begingroup$ The link you provided ragarding the insertion and deletion in a singly-linked list is not stating that this operation is O(n). It clearly says that it's O(1), but if you do not have access to the element preceeding the one you wish to delete, you first have to locate it, which would be an O(n) operation. Certainly insertion and deletion in linked-lists is O(1). The question is whether you already have access to that element. This is a separate concern that generally should not be taken into account when specyfing time complexity in such details you seem to seek. $\endgroup$
    – Fureeish
    Aug 5, 2022 at 16:42
  • $\begingroup$ We are talking about removing a node that we have access to. In the case of singly-linked list it is O(N) because although you can access the node to remove in O(1), then you need to search for the previous node in O(N). $\endgroup$
    – EgonBolton
    Aug 5, 2022 at 20:01

1 Answer 1

Reset to default
1
$\begingroup$

I worry that you are asking for learning and insight without putting in the work that it requires. Having a "quick hit" explanation of some phenomenon doesn't mean that you actually understand it. Whatever is wrong with reading fourteen wikipedia pages? What is wrong with finding a good book on algorithms and data structures and doing a lot of the exercises in it? That is how learning is attained.

Shallow knowledge won't take you very far.

There is a book I like a lot, though it is old and now (sometimes) expensive unless you can find a used copy (or a library copy). The Science of Programming: David Gries. David was once a mentor of mine and I learned a huge amount from his work. It is actually a book about programming, as the name implies, but it has a lot to say about data structures and efficiency of algorithms.

The big idea in the book is programming with pre and post-conditions and program invariants. Big, big idea.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Certainly a table is not going to save me the time of reading all the data structures; I just wanted to know if there was a well-done summary or table that would serve as a starting point. Maybe I didn't express myself well. Thanks for recommending that book, I'll check it out! $\endgroup$
    – EgonBolton
    Aug 5, 2022 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.