DEV Community

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 Voronianskii

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 Voronianskii

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 Voronianskii • Edited

Yeah! for this operation I meant