Run three common loop shapes on the same input, and see how differently they grow.
What to build
A program that counts how many times three loops run.
Requirements
- Count the steps of a single loop over
n. - Count the steps of two nested loops that visit each pair
i < jonce. - Count how many times
ncan be halved before it reaches 1.
Input
One number n.
Output
One line with the three counts, separated by spaces.
Constraints
1 ≤ n ≤ 200.
Example
Input:
8
Output:
8 28 3
Why it works
The three counts are n, n(n − 1) / 2 and about log₂ n. For n = 100 they are 100, 4950 and 6, which shows how differently O(n), O(n²) and O(log n) grow.
Examples
Example 1 · Input
8
Expected output
8 28 3
Example 2 · Input
1
Expected output
1 0 0
Hints
Hint 1
Use one counter per loop, and add 1 inside the loop body.
Hint 2
The third loop divides `m` by 2 each time and stops when `m` is 1.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n;
scanf("%d", &n);
int single = 0, pairs = 0, halvings = 0;
for (int i = 0; i < n; i++) single++;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) pairs++;
for (int m = n; m > 1; m /= 2) halvings++;
printf("%d %d %d\n", single, pairs, halvings);
return 0;
}