CODEWITHSUNDEEP
algorithmtime-complexity
user3740951
user3740951

Reputation: 1239

Runtime complexity of Floyd's cycle detection

According to some online sources I referred the runtime complexity of Floyd's cycle detection algo is O(n). Say,

p = slow pointer
q = fast pointer
m = the distance from start of linked list to first loop node
k = the distance of the meeting point of fast and slow nodes from the first loop node 
l = length of loop
rp = number of loop rotations by p before meeting q.
rq = number of loop rotations by q before meeting p.

Run time complexity should be = m+rp*l+k How does this value be O(n)?

Upvotes: 18

Views: 10111

Answers (3)

mohamed kamal
mohamed kamal

Reputation: 1

When slow reaches first node of cycle fast will be inside at position x now we can write this equation for meeting point i_mod_n=(x+2*i)_mod_n where i is a counter, when solved we get i =n-x which is less than one cycle for slow pointer

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59253

If the list has N nodes, then in <= N steps, either the fast pointer will find the end of the list, or there is a loop and the slow pointer will be in the loop.

Lets say the loop is of length M <= N: Once the slow pointer is in the loop, both the fast and slow pointers will be stuck in the loop forever. Each step, the distance between the fast and the slow pointers will increase by 1. When the distance is divisible by M, then the fast and slow pointers will be on the same node and the algorithm terminates. The distance will reach a number divisible by M in <= M steps.

So, getting the slow pointer to the loop, and then getting the fast and slow pointers to meet takes <= N + M <= 2N steps, and that is in O(N)

In fact, you can get a tighter bound on the step count if you note that when there's a loop, the slow pointer will get to it in N - M steps, so the total step count is <= N.

Upvotes: 46

user2357112
user2357112

Reputation: 281476

If there are n nodes, the slow pointer is guaranteed to travel no more than n steps before the fast pointer either meets the slow pointer or finds an end to the list. That means you do O(n) work advancing the slow pointer, and you advance the fast pointer about twice that, which is also O(n). Thus, the whole algorithm is O(n).

Upvotes: 7

Related Questions