DEV Community

loading...

Discussion on: Java Data Structures

Collapse
hamidur01 profile image
Hamidur Rahman

Time complexity of TreeSet guarantees O(log n) not O(n)

Collapse
vrnsky profile image
Yegor Voronyansky Author

Oh, thank. You are true.

Collapse
hamidur01 profile image
Hamidur Rahman

Since LinkedHashSet is designed/implemented on a HashTable Structure it is possible to be O(1) but it can easily be O(n) depending on a hash()

Thread Thread
vrnsky profile image
Yegor Voronyansky Author

At the docs.oracle.com/javase/7/docs/api/... we see that is provide contant time for basic operation, and O(n) for iteration over a LinkedHashSet that means next require time proportional to the size of the set

Thread Thread
hamidur01 profile image
Hamidur Rahman

Then I think you meant constant time O(1) for add, contains, and remove. Iteration on any structure is always O(n).

Thread Thread
vrnsky profile image
Yegor Voronyansky Author • Edited

Yeah! for this operation I meant