#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
/*
Architecture notes:
-------------------
This program demonstrates several common time complexities using small,
focused functions. Each function is isolated so it can be tested independently.
The main() function runs multiple test cases to show behavior and edge cases.
Performance notes:
------------------
- All examples use standard library containers and algorithms.
- Memory usage is small and predictable.
- No dynamic allocations except those inside std::vector.
- Error handling uses exceptions where appropriate.
- Comments explain complexity, pitfalls, and reasoning.
Security notes:
---------------
- No raw pointers or manual memory management.
- No unsafe casts.
- Input validation is demonstrated in some functions.
*/
// ------------------------------------------------------------
// O(1) — Constant time
// ------------------------------------------------------------
int getFirstElement(const std::vector<int>& data) {
// Accessing an element by index is constant time.
// Pitfall: must check for empty container to avoid undefined behavior.
if (data.empty()) {
throw std::runtime_error("Cannot access first element of an empty vector.");
}
return data[0];
}
// ------------------------------------------------------------
// O(n) — Linear time
// ------------------------------------------------------------
int sumLinear(const std::vector<int>& data) {
// Summing all elements requires visiting each element once.
// Complexity: O(n)
int sum = 0;
for (int x : data) {
sum += x;
}
return sum;
}
// ------------------------------------------------------------
// O(log n) — Logarithmic time
// ------------------------------------------------------------
bool containsBinarySearch(const std::vector<int>& sortedData, int target) {
// std::binary_search runs in O(log n).
// Pitfall: requires sorted input.
return std::binary_search(sortedData.begin(), sortedData.end(), target);
}
// ------------------------------------------------------------
// O(n log n) — Typical sorting complexity
// ------------------------------------------------------------
void sortData(std::vector<int>& data) {
// std::sort uses introsort: average O(n log n).
std::sort(data.begin(), data.end());
}
// ------------------------------------------------------------
// O(n²) — Quadratic time
// ------------------------------------------------------------
bool hasDuplicate(const std::vector<int>& data) {
// Naive duplicate check: compare each pair.
// Complexity: O(n²)
for (size_t i = 0; i < data.size(); ++i) {
for (size_t j = i + 1; j < data.size(); ++j) {
if (data[i] == data[j]) {
return true;
}
}
}
return false;
}
// ------------------------------------------------------------
// Utility: print vector
// ------------------------------------------------------------
void printVector(const std::vector<int>& v) {
std::cout << "[ ";
for (int x : v) std::cout << x << " ";
std::cout << "]";
}
// ------------------------------------------------------------
// Main — multiple test cases
// ------------------------------------------------------------
int main() {
try {
std::cout << "=== Big O Notation Demonstration in C++ ===\n\n";
// Test data
std::vector<int> data = {5, 3, 8, 1, 9};
std::vector<int> sortedData = data;
sortData(sortedData); // prepare sorted version
// -------------------------
// O(1)
// -------------------------
std::cout << "O(1) test: first element of ";
printVector(data);
std::cout << " -> " << getFirstElement(data) << "\n";
// Edge case: empty vector
try {
std::vector<int> empty;
getFirstElement(empty);
} catch (const std::exception& e) {
std::cout << "O(1) edge case: " << e.what() << "\n";
}
// -------------------------
// O(n)
// -------------------------
std::cout << "O(n) test: sum of ";
printVector(data);
std::cout << " -> " << sumLinear(data) << "\n";
// -------------------------
// O(log n)
// -------------------------
std::cout << "O(log n) test: binary search for 8 in ";
printVector(sortedData);
std::cout << " -> " << (containsBinarySearch(sortedData, 8) ? "found" : "not found") << "\n";
// -------------------------
// O(n log n)
// -------------------------
std::vector<int> unsorted = {10, 2, 7, 4, 6};
std::cout << "O(n log n) test: sorting ";
printVector(unsorted);
sortData(unsorted);
std::cout << " -> ";
printVector(unsorted);
std::cout << "\n";
// -------------------------
// O(n²)
// -------------------------
std::vector<int> dupTest = {1, 2, 3, 2};
std::cout << "O(n²) test: duplicate check in ";
printVector(dupTest);
std::cout << " -> " << (hasDuplicate(dupTest) ? "duplicate found" : "no duplicates") << "\n";
// Edge case: no duplicates
std::vector<int> noDup = {1, 2, 3, 4};
std::cout << "O(n²) edge case: ";
printVector(noDup);
std::cout << " -> " << (hasDuplicate(noDup) ? "duplicate found" : "no duplicates") << "\n";
} catch (const std::exception& e) {
// General error handling
std::cerr << "Fatal error: " << e.what() << "\n";
}
}
/*
run:
=== Big O Notation Demonstration in C++ ===
O(1) test: first element of [ 5 3 8 1 9 ] -> 5
O(1) edge case: Cannot access first element of an empty vector.
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
*/
