Assuming the node is in a singly linked list, what is the runtime complexity of searching for a specific node within a singly linked list?

1.  The runtime is O(n) because in the worst case, the node you are searching for is the last node, and every node in the linked list must be visited.
2.  The runtime is O(nk), with n representing the number of nodes and k representing the amount of time it takes to access each node in memory.
3.  The runtime cannot be determined unless you know how many nodes are in the singly linked list.
4.  The runtime is O(1) because you can index directly to a node in a singly linked list.

Correct Answer:

•  The runtime is O(n) because in the worst case, the node you are searching for is the last node, and every node in the linked list must be visited.