What is Time Complexity

Time complexity tells us how fast or slow an algorithm is as the input grows. It doesn't give the actual time in seconds, but gives a mathematical idea of how performance will scale.

Case 1: One by One Search – O(n)

You have a list of fruits and you're looking for "apple". You start from the beginning and check each fruit until you find it.

• If there are 10 fruits, it might take 5 tries.

• If there are 100 fruits, it might take 50 tries.

The time increases linearly with the number of items. This is called O(n) (read as "order of n").

Case 2: Sorted and Divided – O(log n)

Now imagine all fruits are alphabetically sorted, and instead of going one by one, you go to the middle, check the name, and decide which half to look in next (like a binary search).

• You check fewer and fewer options each time by dividing the list.

This is much faster, and called O(log n).

Case 3: Comparing Every Pair – O(n²)

Suppose you want to compare every fruit with every other fruit to check for duplicates.

• With 10 fruits: 10×10 = 100 checks

• With 100 fruits: 100×100 = 10,000 checks

The time grows like a square of the number of items: O(n²).

How do we really measure Time Complexity?

Time Complexity is measured in form of Asymptotic growth function, for which there are following Asymptotic notations.
Asymptotic notation tells us how an algorithm performs when the input size grows, especially for large inputs.

It’s like saying:

“I don’t care how fast your car is in the first few meters. I want to know how it performs on a long highway.”

There are five Asymptotic Notations.

1. Big Oh (O): It provides Upper Bound

2. Big Omega (Ω): It provides Lower Bound

3. Theta (Θ): It provides Tight Bound

4. Little Oh (o): It provides Strictly Upper Bound

5. Little Omega (ω): It provides for Strictly Lower

   

   Generally, Big-Oh(O), Big Omega(Ω), and Theta(Θ) asymptotic notations are used to describe rate of growth of a function or an algorithm.

   There are possible three case about algorithm to grow.

   1. Best Case

   2. Worst Case

   3. Average Case

      

      

      An exercise from Chapter 3; page 61, for asymptotic Notations from Introductiontoalgorithms-3rd Edition (CLRS) book

      

      For a rough estimation of functions in terms of order of their growth functions, some standard functions may be helpful.

      

      Understanding time complexity is like learning the speed limits of different algorithms — it helps us write efficient code, solve problems faster, and make better choices in real-world computing. Keep exploring, keep optimizing!