CODEWITHSUNDEEP
algorithmlistdata-structureslinked-listsingly-linked-list
L.I.B L.I.B
L.I.B L.I.B

Reputation: 77

Finding a node in singly linked list time complexity

I have this question in my DSA Course Mid-term test:

Consider a Single Linked List contains N nodes (N > 8), a method f1() is designed to find the 8th node from beginning, and method f2() is designed to find the 8th node from end. Which is the time complexity of f1() and f2()?

Select one:

a. O(N) and O(N)

b. O(1) and O(1)

c. O(1) and O(N)

d. O(N) and O(1)

The correct answer given is c. O(1) and O(N). However I think that the correct answer is a. I know if N = 8 it will take O(1) time to find the 8th node from the beginning (just return the tail node) but in this case N > 8. Could any one explain this for me please?

Thank you in advance for any help you can provide.

Upvotes: 1

Views: 9018

Answers (1)

attaboy182
attaboy182

Reputation: 2079

O(1) implies constant running time. In other words, it doesn't depend on the input size.

When you apply that definition here, you can see that fetching the 8th element is always a constant operation irrespective of the input size. This is because, irrespective of the size of the input (ex:10,100,100..), the operation get(8) will always take the same time. Also, since we know for sure that n > 8, there's no chance that trying to fetch the 8th element will result in going beyond the size of the input.

Upvotes: 1

Related Questions