I am a programmer at Axa and me and my team have an interesting question for you.
Where can I find the Big O for every method in the package java.lang.util. I don抰 understand why there is no javadoc tag for this crucial information.
How can I be absolutely sure that methods of the ArrayList class give me my response in O(1) ?
> I am a programmer at Axa and me and my team have an
> interesting question for you.
>
> Where can I find the Big O for every method in the
> package java.lang.util. I don抰 understand why there
> is no javadoc tag for this crucial information.
Because it depends on the method. If someone wants to provide this info it would go in the method comment.
> How can I be absolutely sure that methods of the
> ArrayList class give me my response in O(1) ?
You can't because it doesn't. ArrayList.contains() is O(N). A binary search on a sorted ArrayList using Collections.binarySearch() is
(From the API) "This method runs in log(n) time for a "random access" list"
If you want O(1) time complexity your should use HashSet or HashMap.
the answers to the big O questions are quite straight forward.
what operations in particular are you unsure about ?
HashMaps/HashSets have amortized O(1) time complexity, which should
never degenerate. Another issue might be overlong hashCode computations.
Keep in mind that you need to override equals when you override
hashCode(). Usually one gets away just fine without overridding
either one.
Regards,
> HashMaps/HashSets have amortized O(1) time complexity,
> which should
> never degenerate. Another issue might be overlong
> hashCode computations.
> Keep in mind that you need to override equals when you
> override
> hashCode(). Usually one gets away just fine without
> overridding
> either one.
However if you write a bad hash function then those objects will have time complexity higher than O(1). An example of a bad (but valid) hash function ispublic int hashCode() { return 0; }
> > HashMaps/HashSets have amortized O(1) time
> complexity,
> > which should
> > never degenerate. Another issue might be overlong
> > hashCode computations.
> > Keep in mind that you need to override equals when
> you
> > override
> > hashCode(). Usually one gets away just fine without
> > overridding
> > either one.
>
> However if you write a bad hash function then those
> objects will have time complexity higher than O(1).
> An example of a bad (but valid) hash function
> ispublic int hashCode() { return 0; }
that is a very good point indeed.
another scenario where a hash function might degenerate performance
is when the computation of the hash function takes significantly long.
(for example it may require scanning each element of a string's character array or scanning each memeber of a collection).
so the big O times get spoiled by the hashcode functions sometimes.
however an immutable object won't have to compute the hashcode more than once (at the expense of storing an extra int).
regards, stepan