Time Complexity Guidelines
Common time complexity notations:
Input size Required time complexity
• O(1): Constant Time
n ≤ 10 O(n!)
• O(log n): Logarithmic Time
• O(n): Linear Time n ≤ 20 O(2ⁿ)
• O(n log n): Linearithmic Time
n ≤ 500 O(n³)
• O(n²): Quadratic Time
• O(2ⁿ): Exponential Time n ≤ 5000 O(n²)
• O(n!): Factorial Time
n ≤ 10⁶ O(n log n) or O(n)
n is large O(1) or O(log n)
Understanding these constraints helps select appropriate data structures and algorithms for competitive programming problems.
Sorting Algorithms
Basic Sorting
Bubble Sort, Insertion Sort, Selection Sort - typically O(n²) time
complexity
Merge Sort
Divide and conquer algorithm with O(n log n) time complexity
Recursively divides array, sorts subarrays, then merges them
STL sort()
Library function that sorts arrays and other data structures
Efficient implementation with O(n log n) complexity
Resources: GeeksforGeeks Sorting Algorithms and Algorithm Visualizer
Vectors in C++
Definition Creating Vectors
A vector is a dynamic array provided by vector v; // empty vector
STL that can change its size automatically vector v = {2,4,5,2,1};
when elements are added or removed. vector v(10); // size 10, all 0
Advantages vector v(10,5); //size 10,all 5
• Random access to elements
• Automatic size management
• Many useful member functions
Basic Operations
v.push_back(x); // add to end -O(1)
v.pop_back();//remove from end O(1)
[Link](); // get size
[Link](); // remove all elements
Vector Operations & Iterators
Vector Functions Iterators
• v.push_back(x) - Add element to end Variables that point to elements in data
• v.pop_back() - Remove last element structures
• [Link]() - Access last element • [Link]() - Points to first element
• [Link]() - Remove all elements • [Link]() - Points to position after last
• [Link](position) - Delete at position element
• [Link](position, value) - Insert at • [Link]() - Points to last element
position (reverse)
• [Link]() - Points to position before
first element
Iterator Functions
• sort([Link](), [Link]()) - Sort array
• reverse([Link](), [Link]()) - Reverse array
• max_element([Link](), [Link]()) - Find maximum
• min_element([Link](), [Link]()) - Find minimum
Pairs, Tuples & Sets
Pairs & Tuples Sets
Set maintains a collection of
// Pair example
unique elements in sorted order.
pair p(1, "Hello");
• set s; - Creates a sorted set
cout << [Link] << " " << [Link];
• [Link](x); - Insert element -
// Tuple example
O(log n)
tuple t(1, "Hello", 3.14);
• [Link](x); - Remove element -
cout << get<0>(t) << " " << get<1>(t);
O(log n)
• [Link](x); - Check if element
exists
Vector of pairs and tuples can be • s.find(x); - Find element
created for more complex data unordered_set uses hashing with
structures. O(1) average operations.
Maps & Priority Queues
Maps
Key-value pairs with unique keys, similar to dictionaries in Python.
map m;
m["Sayan"] = 31;m["Ankit"] = 23;
// Access: m["Sayan"] returns 31
// Check: [Link]("Sayan") returns 1
unordered_map uses hashing with O(1) average operations.
Priority Queues
Maintains elements with priority ordering.
priority_queue pq; // Max heap
[Link](3);
[Link](5);[Link](1);
// [Link]() returns 5 (maximum element)
// For min heap:priority_queue, greater> pq;
Operations: push - O(log n), pop - O(log n), top - O(1)
Additional Data Structures
Stack & Queue
Deque
Stack: LIFO (Last In First Out)
Dynamic array that can be
efficiently changed at both structure
ends. stack st;
[Link](1); [Link](2);
deque dq;
[Link]();
dq.push_back(1);
// Returns [Link]();
// [1]
// Removes 2
dq.push_front(2);
Queue: FIFO (First In First Out)
// [2,1]
structure
dq.pop_back();
queue q;[Link](1);
// [2]
[Link](2);[Link]();
dq.pop_front();
// Returns 1
// []
[Link]();
// Removes 1
Putting It All Together
Understand the Problem
Analyze constraints to determine appropriate data structures and algorithms.
Choose Efficient Tools
Select the right STL containers and algorithms based on time complexity requirements.
Implement Solution
Use STL to write clean, efficient code rather than implementing everything from scratch.
Practice & Improve
Try introductory problems using what you've learned in this session.
"FRIEND LOOKING AT MY CODE: WHY DIDN'T YOU USE THE METHOD IN THE STANDARD LIBRARY?"
ME AFTER SPENDING 3 HOURS CODING A CUSTOM IMPLEMENTATION: 😭
Thanks for watching! Happy Coding!