#include <iostream>
#include <vector>
#include <chrono>
#include <numeric>
/*
Approximating Big O in Idiomatic C++
-----------------------------------
Big O cannot be computed automatically by C++.
But we *can* approximate it by measuring how runtime
grows as input size increases.
Method:
1. Choose an algorithm to test.
2. Run it for multiple input sizes (n).
3. Measure execution time using std::chrono.
4. Observe how time scales:
- If time ~ n → O(n)
- If time ~ n^2 → O(n^2)
- If time ~ log n → O(log n)
- etc.
This program tests a simple O(n) algorithm:
Summing all elements in a vector.
*/
// Example algorithm: O(n) summation
long long test_algorithm(const std::vector<int>& data) {
// Summing is linear: each element is visited once.
return std::accumulate(data.begin(), data.end(), 0LL);
}
// Measure runtime of the algorithm for a given n
double measure_time(int n) {
std::vector<int> data(n, 1); // fill with dummy values
auto start = std::chrono::high_resolution_clock::now();
volatile long long result = test_algorithm(data);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> elapsed = end - start;
return elapsed.count(); // seconds
}
int main() {
std::cout << "Approximating Big O by timing growth:\n\n";
// Test sizes
std::vector<int> sizes = {10000, 20000, 40000, 80000, 160000};
for (int n : sizes) {
double t = measure_time(n);
std::cout << "n = " << n << " -> time = " << t << " seconds\n";
}
std::cout << "\nInterpretation:\n";
std::cout << "If time roughly doubles when n doubles, the algorithm is O(n).\n";
std::cout << "If time quadruples when n doubles, it's closer to O(n^2).\n";
}
/*
run:
Approximating Big O by timing growth:
n = 10000 -> time = 0.00010758 seconds
n = 20000 -> time = 0.00020989 seconds
n = 40000 -> time = 0.00042917 seconds
n = 80000 -> time = 0.00064525 seconds
n = 160000 -> time = 0.00121844 seconds
Interpretation:
If time roughly doubles when n doubles, the algorithm is O(n).
If time quadruples when n doubles, it's closer to O(n^2).
*/
