educative.io

Time complexity is O(N) instead of O(N*K)

Courses
,
#1

I have a question on Pattern: In-place Reversal of a LinkedList, Solution Review: Problem Challenge 1 on the Grokking the Coding Interview: Patterns for Coding Questions course.
Why is the time complexity O(N) instead of O(N*K)?
The first while loop runs N times, and the inner while loop runs K times.

#2

Hello Prasun Guragain,
Let me try to answer your query. The code only traverses the linked list once which is why the time complexity is O(N). The inner loop you refer to traverses the next k elements and then these elements are skipped in the rest of the code because the current node moves on
Hope this answers your query

1 Like