Suppose We Maintain a Linked List of Length N in Random

question 43

Multiple Choice

Suppose we maintain a linked list of length n in random element order. What would be the big-Oh notation for printing out those elements which occur exactly once in the list (without sorting the list) ?

• A) O(1)
• B) O(n)
• C) O(nlog₂n)
• D) O(n²)

---

Definitions:

Sample Space

The set of all possible outcomes or results in a probability experiment.

Random Experiment

An experiment or process for which the outcome cannot be predicted with certainty ahead of time, involving random variables.

Mutually Exclusive

refers to events that cannot occur at the same time in a probabilistic experiment.

P(A)

The probability of an event A occurring.