-1

Most of the cases in competitive programming it is necessary to know about the complexity of a code before use it. We uses different library functions and STL in C++ coding. And there is a beautiful documentation on STL with complexities.

I want to know about the complexities of different built in generic Collections methods (e.g. complexity of java.util.Arrays.sort()) in java. Is there any proper documentation about the complexities in Java all together?

Thanks in advance.

Shikhor Roy
  • 160
  • 1
  • 10
  • Did you even try to read the [documentation](https://docs.oracle.com/javase/8/docs/api/)? It's all in there, including notes on implementation and complexity. – Axel Jan 13 '17 at 10:23
  • The "beautiful documentation" you have mentioned is usually frowned upon here. You are better off with cppreference.com. See http://stackoverflow.com/questions/6520052/whats-wrong-with-cplusplus-com. It's also not the "STL", mind you. See http://stackoverflow.com/a/5205571/3313064 – Christian Hackl Jan 13 '17 at 10:33
  • What I actually wants to know is all about complexity not only the methods documentations. Let me give an example, [link](https://docs.oracle.com/javase/8/docs/api/) shows the documentations of HashMap. let choose a method "get", the article shows me, how does it (get method) work...but where is the complexity of "get" method? does it give me the elements in O(1) complexity or O(n)? @Axel – Shikhor Roy Jan 13 '17 at 10:48
  • Ha ha...!!! OK, It may not be a proper documentation. But What is important for me to know, Is there any resources which helps me for finding the complexities. Thanks. @ChristianHackl – Shikhor Roy Jan 13 '17 at 11:00

1 Answers1

1

Please read official Oracle documentation with attention, for example cite from (https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(byte[]) ) -

Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

As you can see O(n log(n)) is specified

Dewfy
  • 23,277
  • 13
  • 73
  • 121
  • But every time I cant get the complexities. e.g https://docs.oracle.com/javase/7/docs/api/java/util/Map.Entry.html#getKey(), No complexity for getValue() method!!! – Shikhor Roy Jan 13 '17 at 10:29
  • @ShikhorRoy it is because `getValue()` doesn't implement any algorithm - it is just accessor to underlying data – Dewfy Jan 13 '17 at 10:37
  • 1
    @ShikhorRoy even when the time complexity is not specified, it is easy to find out yourself what is the time complexity for a certain method. E.g java uses [Timsot] (https://en.wikipedia.org/wiki/Timsort) for arraylist sorting algorithm. – Niku Hysa Jan 13 '17 at 10:37
  • No!!! it is not the fact what i want to know...Let me explain, getValue() gives me the value of a key...but how does it work? does it give me the value in O(1) or in O(n)? It is important... BTW what you code to do anything is an algorithm...so getValue() obviously an algorithm for getting a value from HashMap. So it must have a Time Complexity. @Dewfy – Shikhor Roy Jan 13 '17 at 10:53
  • OK. But I need to know the complexity of different methods of built in library before use it into competitive programming. Like, ArrayList's Get method works in O(1) complexity according to [this](http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html). As I know the complexity of Get method then I will be confirm...ok...Get method can be used in Competive Programing...I think you get it, what I want to know. @NikuHysa – Shikhor Roy Jan 13 '17 at 11:06
  • What do you mean competitive programming? And no, i don't know what you mean! – Niku Hysa Jan 17 '17 at 08:47