CODEWITHSUNDEEP
javaiteratorcomplexity-theory
user1950055
user1950055

Reputation: 157

Amortised Complexity for Iterators

I am required to implement an iterator function in Java for a balanced tree for example AVL tree with an amortised complexity of O(1+log(N/M)) and am not sure what this means? Any links or explanation will be very helpful..Thanks

Upvotes: 1

Views: 168

Answers (1)

iGili
iGili

Reputation: 883

It means that for every consecutive call to the iterator's next() method, the complexity of that method call will decrease. for a tree with N nodes, the first call should have a complexity of O(log(N)), the following invocation should have O(log(N/2)), etc. to really understand complexity you should have some background in mathematics and computer science. for a short and ambiguous explanation read here. for a deeper understanding of this topic you should start with Corman's Introduction to algorithms

Upvotes: 1

Related Questions