This is a question from Cormen 3rd edition(exercise 10.1). I am of the opinion that the complexity should be O(1), as we just have to look into the next pointer of the current node.

But the answers from the web suggest that it should be O(n). Where am I getting it wrong?

Can someone please help me out???

Thanks in advance!

  • 3
    $\begingroup$ Is the node whose predecessor you want given as input? $\endgroup$ – Reinstate Monica Jun 27 '18 at 18:11

Both answers look wrong. Time is indeed $O(1)$ because you can look into prev (not next) pointer of the node. The answers you found on the web are probably about single-linked lists.


I guess if you include the time it takes you to find a node X and its predecessor, then finding the node would be $O(n)$ and going back once will be $O(1)$, but this sounds unnecessary since we can directly find the predecessor.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.