Majority Element Moore's Voting Algorithm in DSA Python - Time & Space Complexity

Time Complexity: Majority Element Moore's Voting Algorithm

O(n)

Understanding Time Complexity

We want to understand how fast Moore's Voting Algorithm finds the majority element in a list.

How does the time needed grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def majority_element(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

This code finds the majority element by counting and updating a candidate as it scans the list once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One loop that goes through each number in the list once.
• How many times: Exactly once for each element, so n times if the list has n elements.

How Execution Grows With Input

As the list gets bigger, the algorithm checks each number once, so the work grows directly with the list size.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of operations grows in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows directly in proportion to the number of elements in the list.

Common Mistake

[X] Wrong: "The algorithm checks pairs or does nested loops, so it must be slower than O(n)."

[OK] Correct: The algorithm only scans the list once, updating counts without extra loops inside, so it stays fast and linear.

Interview Connect

Knowing this algorithm's time complexity shows you can find efficient solutions that scan data once, a skill valued in many coding challenges.

Self-Check

"What if we added a second pass to verify the candidate's count? How would the time complexity change?"