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

Time Complexity: Majority Element Moore's Voting Algorithm

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the majority element grows as the input size increases.

Specifically, how many steps does Moore's Voting Algorithm take when the input array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int findMajorityElement(int arr[], int n) {
    int count = 0, candidate = -1;
    for (int i = 0; i < n; i++) {
        if (count == 0) {
            candidate = arr[i];
        }
        if (arr[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}
    

This code finds the majority element by keeping track of a candidate and its count while scanning the array once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single for-loop scanning the array once.
• How many times: Exactly n times, where n is the array size.

How Execution Grows With Input

As the array size grows, the number of steps grows directly in proportion.

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

Pattern observation: Doubling the input size roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the majority element grows linearly with the size of the input array.

Common Mistake

[X] Wrong: "Since there are two loops in some versions, the time complexity is O(n²)."

[OK] Correct: The algorithm uses only one main loop that runs n times; any second pass is separate and also linear, so overall time is still O(n), not squared.

Interview Connect

Understanding this linear time solution shows you can find efficient answers by clever counting, a skill valued in problem solving.

Self-Check

"What if we added a verification step that counts the candidate's occurrences after finding it? How would the time complexity change?"