#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/*
Architecture notes:
-------------------
This program demonstrates several common time complexities using modular,
standalone functions. Each function is small, predictable, and testable.
The main() function runs multiple test cases, including edge cases.
Performance notes:
------------------
- Uses only standard library functions.
- Avoids unnecessary dynamic memory.
- Demonstrates safe error handling and input validation.
- Comments explain complexity, pitfalls, and reasoning.
Security notes:
---------------
- No unchecked pointer arithmetic.
- No unsafe memory operations.
- All allocations checked for failure.
*/
// ------------------------------------------------------------
// O(1) — Constant time
// ------------------------------------------------------------
int get_first_element(const int *arr, size_t n) {
// Accessing an element by index is constant time.
// Pitfall: must validate size to avoid undefined behavior.
if (n == 0) {
fprintf(stderr, "Error: cannot access first element of an empty array.\n");
return 0; // Return a safe fallback value.
}
return arr[0];
}
// ------------------------------------------------------------
// O(n) — Linear time
// ------------------------------------------------------------
long sum_linear(const int *arr, size_t n) {
// Summing all elements requires visiting each element once.
// Complexity: O(n)
long sum = 0;
for (size_t i = 0; i < n; ++i) {
sum += arr[i];
}
return sum;
}
// ------------------------------------------------------------
// O(log n) — Logarithmic time (binary search)
// ------------------------------------------------------------
bool contains_binary_search(const int *arr, size_t n, int target) {
// Requires sorted input.
// Complexity: O(log n)
size_t left = 0;
size_t right = n;
while (left < right) {
size_t mid = left + (right - left) / 2;
if (arr[mid] == target) return true;
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
return false;
}
// ------------------------------------------------------------
// O(n log n) — Sorting
// ------------------------------------------------------------
int compare_ints(const void *a, const void *b) {
// qsort comparator
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y);
}
void sort_data(int *arr, size_t n) {
// qsort uses O(n log n) average complexity.
qsort(arr, n, sizeof(int), compare_ints);
}
// ------------------------------------------------------------
// O(n²) — Quadratic time
// ------------------------------------------------------------
bool has_duplicate_quadratic(const int *arr, size_t n) {
// Naive duplicate check: compare each pair.
// Complexity: O(n²)
for (size_t i = 0; i < n; ++i) {
for (size_t j = i + 1; j < n; ++j) {
if (arr[i] == arr[j]) return true;
}
}
return false;
}
// ------------------------------------------------------------
// Utility: print array
// ------------------------------------------------------------
void print_array(const int *arr, size_t n) {
printf("[ ");
for (size_t i = 0; i < n; ++i) printf("%d ", arr[i]);
printf("]");
}
// ------------------------------------------------------------
// Main — multiple test cases
// ------------------------------------------------------------
int main(void) {
printf("=== Big O Demonstration in C ===\n\n");
int data[] = {5, 3, 8, 1, 9};
size_t n_data = sizeof(data) / sizeof(data[0]);
int sorted_data[] = {5, 3, 8, 1, 9};
sort_data(sorted_data, n_data);
// -------------------------
// O(1)
// -------------------------
printf("O(1) test: first element of ");
print_array(data, n_data);
printf(" -> %d\n", get_first_element(data, n_data));
// Edge case: empty array
int empty_arr[1];
printf("O(1) edge case: empty array -> ");
get_first_element(empty_arr, 0);
// -------------------------
// O(n)
// -------------------------
printf("O(n) test: sum of ");
print_array(data, n_data);
printf(" -> %ld\n", sum_linear(data, n_data));
// -------------------------
// O(log n)
// -------------------------
printf("O(log n) test: binary search for 8 in ");
print_array(sorted_data, n_data);
printf(" -> %s\n", contains_binary_search(sorted_data, n_data, 8) ? "found" : "not found");
// -------------------------
// O(n log n)
// -------------------------
int unsorted[] = {10, 2, 7, 4, 6};
size_t n_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);
printf("O(n log n) test: sorting ");
print_array(unsorted, n_unsorted);
sort_data(unsorted, n_unsorted);
printf(" -> ");
print_array(unsorted, n_unsorted);
printf("\n");
// -------------------------
// O(n²)
// -------------------------
int dup_test[] = {1, 2, 3, 2};
size_t n_dup_test = sizeof(dup_test) / sizeof(dup_test[0]);
printf("O(n²) test: duplicate check in ");
print_array(dup_test, n_dup_test);
printf(" -> %s\n", has_duplicate_quadratic(dup_test, n_dup_test) ? "duplicate found" : "no duplicates");
// Edge case: no duplicates
int no_dup[] = {1, 2, 3, 4};
size_t n_no_dup = sizeof(no_dup) / sizeof(no_dup[0]);
printf("O(n²) edge case: ");
print_array(no_dup, n_no_dup);
printf(" -> %s\n", has_duplicate_quadratic(no_dup, n_no_dup) ? "duplicate found" : "no duplicates");
return 0;
}
/*
The “ERROR!” is not from your C program.
It is from your environment (terminal, runner, or wrapper script) reacting to the stderr output and prefixing it with ERROR!.
It corresponds to the call: get_first_element(empty_arr, 0);
*/
/*
run:
=== Big O Demonstration in C ===
O(1) test: first element of [ 5 3 8 1 9 ] -> 5
O(1) edge case: empty array -> Error: cannot access first element of an empty array.
O(n) test: sum of [ 5 3 8 1 9 ] -> 26
O(log n) test: binary search for 8 in [ 1 3 5 8 9 ] -> found
O(n log n) test: sorting [ 10 2 7 4 6 ] -> [ 2 4 6 7 10 ]
O(n²) test: duplicate check in [ 1 2 3 2 ] -> duplicate found
O(n²) edge case: [ 1 2 3 4 ] -> no duplicates
All tests completed.
*/
