Activity Selection Problem in DSA C - Time & Space Complexity

Time Complexity: Activity Selection Problem

O(n)

Understanding Time Complexity

We want to understand how the time needed to select activities grows as the number of activities increases.

How does the program's work change when we have more activities to choose from?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Activities sorted by finish time
int selectActivities(int start[], int finish[], int n) {
    int count = 1; // first activity always selected
    int last = 0;
    for (int i = 1; i < n; i++) {
        if (start[i] >= finish[last]) {
            count++;
            last = i;
        }
    }
    return count;
}
    

This code picks the maximum number of activities that don't overlap, assuming activities are sorted by finish time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that checks each activity once.
• How many times: The loop runs (n - 1) times, where n is the number of activities.

How Execution Grows With Input

As the number of activities grows, the program checks each one once in order.

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

Pattern observation: The number of operations grows roughly in a straight line with the number of activities.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly with the number of activities.

Common Mistake

[X] Wrong: "The code checks every pair of activities, so it must be O(n²)."

[OK] Correct: The code only loops once through the list, comparing each activity to the last selected one, not all pairs.

Interview Connect

Understanding this helps you explain how greedy choices can lead to efficient solutions, a key skill in problem solving.

Self-Check

"What if the activities were not sorted by finish time? How would the time complexity change?"