0

I am a student of CS, learning about Java Collections. At my school we have received a chart with with time complexity of different operations on data structures. There are some things in the chart that don't make sense to me.

Linked List It says that time complexity for inserting at the end and finding the number of elements is implementation dependent. Why is that? Why isn't it O(n)?

HashMap For the HashMap it says that tc for finding number of elements or determining whether the hashMap is empty has also tc implementation dependent.

TreeMap same goes for the TreeMap. According to the chart, the tc of the operation to determine the number of elements is implementation dependent. Which implementation do they mean?

Kabachok
  • 573
  • 1
  • 7
  • 22
  • 1
    You can read [this good article](http://www.programcreek.com/2013/03/hashset-vs-treeset-vs-linkedhashset/). – Andrew Tobilko Jun 07 '15 at 15:18
  • @AndrewTobilko Duzhe diakuju! Thank you! – Kabachok Jun 07 '15 at 15:23
  • @Lrrr LinkedList, HashMap and TreeMap are not interfaces, they implement interfaces List and Map as far as I know – Kabachok Jun 07 '15 at 15:32
  • Could someone please explain to me why this kind of question is downvoted? Ok, I understand, it is not the most complex issue of computer science, but as a beginner it is sometimes difficult to understand the nuances, even after reading the API and searching through other answers. We have all been noobs at some point. What is the problem? – Kabachok Jun 07 '15 at 15:41
  • If you hover over the upvote and downvote buttons, a piece of text appears explaining their purpose. In this case, I would imagine it's "does not show any research effort". – Sotirios Delimanolis Jun 07 '15 at 15:44
  • How am I supposed to show it? Write an essay on what I already know on the subject and create a PowerPoint presentation? Or give a list of links I have visited researching the subject with a shot summary? I am not asking to explain to me what a TreeMap is. But anyway, I am getting used to this on StackOverflow. At least there still good people willing to help out without downvoting you to the point you can't post a question anymore. Anyway, I have a right to ask, people have a right to downvote, that's what it boils down to. – Kabachok Jun 07 '15 at 15:50
  • You say _Why isn't it O(n)?_. Stating why you think it should be `O(n)` would be good enough for me (for that example). – Sotirios Delimanolis Jun 07 '15 at 15:51
  • @SotiriosDelimanolis ok, thank you for you input. – Kabachok Jun 07 '15 at 15:52
  • 1
    [HashMap get/put complexity](http://stackoverflow.com/questions/4553624/hashmap-get-put-complexity) gives a good explanation wrt HashMaps/Sets, [Big O summary for java collections implementations](http://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations) also has info on lists and tree maps. – Mick Mnemonic Jun 07 '15 at 16:55

1 Answers1

1

Some implementations of LinkedList can keep a count of the number of elements in their list as well as a pointer to the last element for quick tail insertion. This means that they are done O(1) as it is a quick data access.

Similar reasoning can be followed for implementations of HashMap and TreeSet, if they keep a count of the number of elements with their data structure then functions such as isEmpty() and size() can be done O(1) also.

Brett Walker
  • 3,566
  • 1
  • 18
  • 36