main function and program entry - Time & Space Complexity

Time Complexity: main function and program entry

O(1)

Understanding Time Complexity

We want to understand how the time to run a C program grows when it starts at the main function.

What happens to the program's work as it begins running?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdio.h>

int main() {
    printf("Hello, world!\n");
    return 0;
}
    

This code starts the program and prints a simple message once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single print statement.
• How many times: Exactly once when the program starts.

How Execution Grows With Input

Since the program only prints once, the work does not grow with input size.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The number of operations stays the same no matter the input size.

Final Time Complexity

Time Complexity: O(1)

This means the program runs in constant time, doing the same amount of work regardless of input.

Common Mistake

[X] Wrong: "The main function always takes longer if the program is bigger."

[OK] Correct: The main function itself runs once and does what it is told; its time depends on what code it runs, not the program size.

Interview Connect

Understanding how the main function starts your program helps you think about how programs begin and how their work grows, a key skill for writing efficient code.

Self-Check

"What if the main function called a loop that runs n times? How would the time complexity change?"