Internship← Competitive Programming learning pathCompetitive Programming · Module 2 of 10
Time complexity and constraints
Pick an algorithm whose complexity fits the input size.
📖 Key ideas
- Big-O describes how running time grows with input size n.
- Rule of thumb: about 10^8 simple operations per second.
- n up to 10^5 needs O(n log n) or better; n up to 20 allows O(2^n).
- Nested loops over n give O(n^2).
- Space complexity matters too: 256 MB is a common memory limit.
💡 Real-life example: Choosing an algorithm by n is like choosing a vehicle by distance: walk to the shop, take a train to another city.
O(n)Linear time
O(n log n)Sorting-level time
O(n^2)Two nested loops
O(2^n)All subsets