Structure of a C program - Time & Space Complexity

Time Complexity: Structure of a C program

O(1)

Understanding Time Complexity

Let's see how the time it takes to run a simple C program changes as the program size grows.

We want to know how the program's structure affects how long it runs.

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 prints a message once and then ends.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single print statement.
• How many times: Exactly once, no loops or repeats.

How Execution Grows With Input

Explain the growth pattern intuitively.

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

Pattern observation: The number of operations stays the same no matter how big the input is.

Final Time Complexity

Time Complexity: O(1)

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

Common Mistake

[X] Wrong: "Adding more lines of code always makes the program slower in a way that depends on input size."

[OK] Correct: Some code runs a fixed number of times no matter the input, so its time does not grow with input size.

Interview Connect

Understanding that some parts of a program run in constant time helps you explain how programs behave and write efficient code.

Self-Check

"What if we added a loop that prints the message n times? How would the time complexity change?"

Practice

1. Which part of a C program is mandatory to start the execution of the program?

easy

A. The return statement

B. The printf() statement

C. The #include directive

D. The main() function

Solution

1. Step 1: Understand program entry point

   In C, the program always starts executing from the main() function.

2. Step 2: Identify mandatory part for execution

   Without main(), the program has no defined starting point.

3. Final Answer:

   The main() function -> Option D

4. Quick Check:

   Program starts at main() [OK]

Hint: Look for the function where execution begins [OK]

Common Mistakes:

• Thinking printf() starts the program
• Confusing #include with execution start
• Assuming return starts the program

2. Which of the following is the correct way to include the standard input-output header in a C program?

easy

A. #include "stdio.h"

B. #include

C. include

D. #include stdio.h

Solution

1. Step 1: Recognize correct syntax for header inclusion

   The standard way to include system headers is using angle brackets: #include <header>.

2. Step 2: Check each option

   #include uses correct syntax: #include <stdio.h>. #include "stdio.h" uses quotes which is for user headers. Options C and D miss the # or angle brackets.

3. Final Answer:

   #include <stdio.h> -> Option B

4. Quick Check:

   System headers use <> brackets [OK]

Hint: Use #include with angle brackets for standard headers [OK]

Common Mistakes:

• Using quotes instead of angle brackets for standard headers
• Omitting the # symbol
• Missing angle brackets or quotes

3. What will be the output of the following C program?

#include <stdio.h>

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

medium

A. Hello World

B. hello, world!

C. Hello, World!

D. Syntax Error

Solution

1. Step 1: Analyze the printf statement

   The program prints exactly the string inside quotes: "Hello, World!\n" which means it prints Hello, World! followed by a new line.

2. Step 2: Check for case and punctuation

   The output matches Hello, World! exactly, including capitalization and punctuation.

3. Final Answer:

   Hello, World! -> Option C

4. Quick Check:

   Output matches printf string exactly [OK]

Hint: Match output exactly with printf string [OK]

Common Mistakes:

• Ignoring case sensitivity
• Missing punctuation or newline
• Assuming syntax error without checking code

4. Identify the error in the following C program:

#include <stdio.h>

int main() {
    printf("Welcome to C programming!");
}

medium

A. Missing return statement in main function

B. Missing semicolon after printf statement

C. Incorrect header file included

D. No error, program is correct

Solution

1. Step 1: Check syntax of printf statement

   The printf line ends with a semicolon, so no syntax error there.

2. Step 2: Check main function return

   The main function is declared to return int but lacks a return statement, which can cause a warning or error depending on compiler settings.

3. Final Answer:

   Missing return statement in main function -> Option A

4. Quick Check:

   main() must return int value [OK]

Hint: Always include return 0; in main() [OK]

Common Mistakes:

• Assuming missing semicolon error
• Ignoring missing return in main
• Thinking header file is wrong

5. You want to write a C program that prints numbers from 1 to 5 using a loop inside the main() function. Which of the following code snippets correctly shows the structure of such a program?

hard

A. #include

int main() {
int i;
for(i = 1; i <= 5; i++) {
printf("%d\n", i);
}
return 0;
}

B. #include

void main() {
int i;
for(i = 1; i < 5; i++) {
printf("%d\n", i);
}
}

C. #include

int main() {
int i = 1;
while(i < 5) {
printf("%d\n", i);
i++;
}
return 0;
}

D. #include

int main() {
int i;
for(i = 1; i <= 5; i++)
printf("%d\n", i);
}

Solution

1. Step 1: Check loop range and printing

   #include int main() { int i; for(i = 1; i <= 5; i++) { printf("%d\n", i); } return 0; } uses a for loop from 1 to 5 inclusive, printing each number with newline, which matches the requirement.

2. Step 2: Verify program structure and correctness

   #include int main() { int i; for(i = 1; i <= 5; i++) { printf("%d\n", i); } return 0; } has correct int main(), includes return 0;, and proper syntax. Other options have issues: B uses void main() (not standard), loop range is incorrect; C loops only to 4; D misses braces which is allowed but less clear.

3. Final Answer:

   Option A is the correct and complete program structure -> Option A

4. Quick Check:

   Correct loop and main() structure [OK]

Hint: Use int main() with return 0 and correct loop range [OK]

Common Mistakes:

• Using void main() instead of int main()
• Incorrect loop range (less than 5)
• Omitting return statement
• Missing braces causing confusion