On Sep 5, 11:07 am, jliang <[EMAIL PROTECTED]> wrote:
> how about a doubled linked list where you can remove item at any
> index. the removing is O(1). you can also keep track of the current
removing from a doubled linked list is O(1)? How?
> size S so if you are borrowing book at index greater than S/2, you
> traverse the list from the end, if index < S/2, you traverse from the
> beginning.
>
> every time a book is removed, S becomes 1 smaller, so the traversal
> time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1
>
> you can also put them in a binary tree, so every operation is O(lgN)
putting the original array in binary tree takes O(M lgM) time, and you
will lose the original indices. So it's of no use.
> so the total will be O(lgN M)
I dont think so. correct me if I am wrong.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
