Finding a node in singly linked list time complexity

Question

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.

The answer given is correct, you are not. How many operations do you need to return the 8th node out of 1000? Out of 1000000? — n. m. could be an AI
– n. m. could be an AI, Commented May 18, 2016 at 14:42
c. is the most correct, but a. is also technically correct, since anything that's O(1) is also O(N). — Paul Hankin
– Paul Hankin, Commented May 19, 2016 at 1:20

attaboy182 · Accepted Answer · 2016-05-18 14:55:02Z

1

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.

edited May 18, 2016 at 14:55

answered May 18, 2016 at 14:51

attaboy182

2,0993 gold badges22 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Paul Hankin Over a year ago

O(1) doesn't imply constant running time, nor that the time doesn't depend on the input size. Rather, it implies that the running time is bounded by a constant.

attaboy182 Over a year ago

@PaulHankin the whole point was trying to make someone understand O(1) . There's a reason I used the word imply.

Paul Hankin Over a year ago

Sure, but there's a lot of misunderstanding of big-O and complexity and I don't think that good answers need to include errors. Perhaps: "O(1) means that the program never takes more than a fixed amount of time, no matter the input."

Collectives™ on Stack Overflow

Finding a node in singly linked list time complexity

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related