> ## Documentation Index
> Fetch the complete documentation index at: https://docs.hnuicpc.tech/llms.txt
> Use this file to discover all available pages before exploring further.
# Functions, structs, and time complexity
> Tutorial for Sheet 4 — Learn about functions, structs, pairs, and how to analyze time complexity.
## Functions
Functions help you organize code, avoid repetition, and make your solutions cleaner.
### Defining functions
```cpp theme={null}
// Function with return value
int add(int a, int b) {
return a + b;
}
// Void function (no return)
void printArray(vector& v) {
for (int x : v) cout << x << " ";
cout << "\n";
}
// Function with default parameters
int power(int base, int exp = 2) {
int result = 1;
for (int i = 0; i < exp; i++) result *= base;
return result;
}
```
### Pass by reference vs value
```cpp theme={null}
// Pass by value — creates a copy (slow for large data)
void modify(int x) {
x = 10; // Original is NOT changed
}
// Pass by reference — modifies the original (fast)
void modify(int& x) {
x = 10; // Original IS changed
}
// Pass by const reference — fast, read-only
int sum(const vector& v) {
int s = 0;
for (int x : v) s += x;
return s;
}
```
Always pass vectors and strings **by reference** (`&`) to avoid copying. Use `const&` if you don't need to modify them.
## Structs
Structs let you group related data together.
```cpp theme={null}
struct Point {
int x, y;
};
struct Student {
string name;
int grade;
double gpa;
};
int main() {
Point p = {3, 4};
cout << p.x << " " << p.y;
Student s;
s.name = "Ahmed";
s.grade = 95;
// Array of structs
vector students(n);
for (int i = 0; i < n; i++) {
cin >> students[i].name >> students[i].grade;
}
}
```
### Sorting structs
```cpp theme={null}
struct Event {
int start, end;
};
// Custom comparator
bool cmp(Event a, Event b) {
return a.end < b.end; // Sort by end time
}
sort(events.begin(), events.end(), cmp);
// Or with lambda
sort(events.begin(), events.end(), [](Event& a, Event& b) {
return a.start < b.start;
});
```
## Pairs and tuples
```cpp theme={null}
// Pair — holds two values
pair p = {3, 5};
cout << p.first << " " << p.second;
// make_pair
pair student = make_pair("Ahmed", 95);
// Vector of pairs
vector> edges;
edges.push_back({1, 2});
// Pairs sort by first, then by second automatically
sort(edges.begin(), edges.end());
// Tuple — holds three or more values
tuple t = {1, 2, 3};
cout << get<0>(t) << get<1>(t) << get<2>(t);
```
## Time complexity
Understanding time complexity tells you **whether your solution will pass** within the time limit.
### Big-O notation
| Complexity | Name | Max n (≈ 1 sec) | Example |
| ---------- | ------------ | --------------- | ------------------- |
| O(1) | Constant | Any | Array access, math |
| O(log n) | Logarithmic | 10¹⁸ | Binary search |
| O(n) | Linear | 10⁸ | Single loop |
| O(n log n) | Linearithmic | 10⁶ | Sorting |
| O(n²) | Quadratic | 10⁴ | Nested loops |
| O(n³) | Cubic | 500 | Triple nested loops |
| O(2ⁿ) | Exponential | 20–25 | Subsets |
| O(n!) | Factorial | 10–12 | Permutations |
### How to estimate
The rule of thumb: **10⁸ simple operations per second**.
```
n ≤ 10 → O(n!) or O(2ⁿ) is fine
n ≤ 20 → O(2ⁿ) is fine
n ≤ 500 → O(n³) is fine
n ≤ 5000 → O(n²) is fine
n ≤ 10⁶ → O(n log n) is needed
n ≤ 10⁸ → O(n) is needed
n > 10⁸ → O(log n) or O(1) is needed
```
Before coding, **always check the constraints** and calculate if your approach is fast enough. A TLE (Time Limit Exceeded) means your algorithm is too slow.
### Analyzing loops
```cpp theme={null}
// O(n)
for (int i = 0; i < n; i++) { ... }
// O(n²)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) { ... }
// O(n log n)
sort(v.begin(), v.end());
// O(log n)
while (n > 0) { n /= 2; }
```
## Practice
Practice problems for this tutorial.