Time Complexity
Big-O ,Big-theta and Big-omega
✨ About Me Hi 👋, I’m Sakshi, a tech enthusiast and beginner blogger passionate about learning and sharing technology in a simple way. TechNotes by Sakshi is a place where I write easy-to-understand notes and blogs on: 💻 Programming basics 🌐 Web development (HTML, CSS, basics)
One morning I wanted to eat some pizza , so i asked my brother to get me some from pizza hut which is near 2 km. He got me the pizza and I was happy only to realise it was too less for 29 friends who came to my have for a surprise visit!
My brother can get 3 pizza for me on his bike but pizza for 29 friends is too huge of an input for him which he cannot handle.
2 pizza ——→ okya not a big deal !
29 pizza ———> not possible in short time.
WHAT IS TIME COMPLEXITY?
Time Complexity is the study of efficiency of algorithms.
Time Complexity = How time taken to execute an algorithm grows with the size of the input !
Consider two develops who created an algorithm to sort n number .Sakshi and Ankit did this independently.
when ran for input size n, following result were recorded.
| Input Size (n) | Sakshi’s Algo (ms) | Ankit’s Algo (ms) |
| 10 | 90 | 122 |
| 70 | 110 | 124 |
| 110 | 130 | 128 |
| 10000 | 200 | 135 |
quiz : Who’s Algorithm is better?
Time Complexity : Sending GTA 5 to a friend
Let us say you have a friend living 5 ks away from from your place. You want to send him a game.
Final exams are over and you want him to get this 60 GB file from you. How will you send it to him?
Note that both of you are using jio 4G with 1 Gb/day data limit.
The best way to send him the game is by delivering it to his house. copy the game to a Hard disk and send it !
Will you do the same thing for sending a game like minesweeper which is in kbs of size ?
—> no because you can’t send it via internet.
As the file Size grows , time taken by online sending increases linearly —>’o(n)’
As the file size grows , time taken by physical sending remains constant O(n°) or O(1).
Calculating Order in Terms of Input size.
In order to Calculate the order , most impactful term containing n is taken into account.
Let us assume that formula of an algorithm in terms of input size n looks like this.
Algo 1 → k₁ n² + k₂ n+ 36 =>O(n²)
//k₁ n² is the highest order term//
Algo 2 → k₁k₂+ k₃k₂ +8
// k₁k₂n° + k₃k₂ +8 =>O(n°) or O(1).
Note that there are the formula for time taken by them.
Why constants don’t matter in Time Complexity
In real systems, execution time depends on hardware, compiler, and background processes.
That’s why we ignore constants like k₁ , k₂, or 36 and focus only on how the algorithm behaves as input size n grows.
The goal of time complexity is growth comparison, not exact time calculation.
Common Time Complexities You Should Know
O(1) – Constant time (Example: accessing an array element)
O(log n) – Logarithmic time (Binary Search)
O(n) – Linear time (Traversing a list)
O(n log n) – Efficient sorting (Merge Sort, Quick Sort avg case)
O(n²) – Nested loops (Bubble Sort, Selection Sort)
Best, Average, and Worst Case Time Complexity
Best Case – Minimum time required
Average Case – Expected time for random input
Worst Case – Maximum time taken
In real life, we usually care about the worst case, because it guarantees performance under all conditions.
Conclusion
Time complexity helps us choose algorithms that scale well.
Just like your brother can handle 2 pizzas but not 29, some algorithms work well for small inputs but fail badly for large ones.
Understanding time complexity helps us write efficient, scalable, and professional code.