- What Is Complexity in an Algorithm?
- Types of Algorithm Complexity
- 1. Time complexity – How Fast is Your Algorithm?
- Simple Analogy:
- Real Example:
- Linear Search:
- Binary Search (sorted array):
- 2. Space Complexity
- Analogy
- 📖 Example: Organizing a Bookshelf
- Organizing a Bookshelf
- Scenario 1: Linear Search
- Scenario 2: Using an Alphabetically Sorted Bookshelf (Binary Search)
- Understanding Through The Example
- Balancing Time and Space
- Important Points to Remember
- Real-World Analogy
- Conclusion
- FAQs
- Q1. Which is more important: time or space complexity?
- Q2. What is O(n)?
- Q3. Can an algorithm have O(1) time and O(n) space?
When solving problems using code, there’s often more than one way to reach a solution. But how do we know which approach is the best? This is where the complexity of an algorithm comes into play.
In simple terms, algorithm complexity helps us measure how efficient a program is in terms of time taken (Time Complexity) and memory used (Space Complexity). These two factors are critical for writing optimized, scalable, and high-performance applications — especially when dealing with large inputs or limited system resources.
Imagine you’re building something with LEGO. Some instructions help you build quickly (fast algorithm), while others are slow and confusing (inefficient algorithm). You want the fast, easy one, right? That’s what complexity helps you figure out.
What Is Complexity in an Algorithm?
The complexity of an algorithm is all about measuring:
- ⏱️ Time → How long does it take to run?
- 💾 Space → How much memory does it need?
So when someone says:
“The algorithm has a time complexity of O(n)”,
They’re saying:
“As the number of inputs increases, the time to finish the task grows linearly.”
Types of Algorithm Complexity
- Time Complexity
- Space Complexity
1. Time complexity – How Fast is Your Algorithm?
It evaluates how efficiently the algorithm works as the size of input increases in comparison with its alternate algorithms/solutions. The size of input we consider here varies from 1 to millions and sometimes billions.
Definition:
Time complexity refers to the amount of time an algorithm takes to complete based on the input size (n
).
Simple Analogy:
Imagine you are searching for your favorite toy in a toy box:
- If the box has only 5 toys, you’ll find it quickly.
- If it has 5000 toys? You’re going to spend a lot more time!
That’s how time complexity works — it grows with the input size.
Real Example:
You’re given an array of 100 elements, and you want to find one number.
Linear Search:
- Checks each element one by one.
- Worst Case Time Complexity: O(n)
Binary Search (sorted array):
- Divides the array in half each time.
- Worst Case Time Complexity: O(log n)
So, binary search is faster — but it only works on sorted arrays.
2. Space Complexity
Here, the term memory is used as space. It evaluates the amount of extra memory used to reach a solution. Whenever the code is executed, some memory is provided to the text/code written, and extra memory is allocated to each variable and data structure used in the program.
For Example, if we need to add N integers and for this purpose, we are creating a variable for each integer, these N variables will have their own N memory location. The space complexity will become O(N) (read as the order of N).
Definition:
Space complexity refers to the extra memory your algorithm uses while solving the problem.
This includes:
- Variables
- Data structures
- Function call stack
- Temporary arrays or buffers
Analogy
Let’s say you want to clean your room:
- Method 1: Toss everything into one big box. Quick and uses a big box (high space).
- Method 2: Sort everything neatly into drawers. Takes time, but uses space smartly.
The same goes for space complexity — you either use more memory and finish faster, or you manage with little memory and take more time.
📖 Example: Organizing a Bookshelf
Organizing a Bookshelf
Imagine you have a bookshelf with 100 books, and you’re looking for one specific book. The way you search for this book can illustrate both time and space complexity.
Scenario 1: Linear Search
Time Complexity: In this scenario, you start at one end of the bookshelf and check each book one by one until you find the book you’re looking for. If your book happens to be at the very end, you would have checked 100 books to find it. In the worst case, the time it takes to find your book grows linearly with the number of books on the shelf. This is an example of linear time complexity, often noted as O(n), where “n” is the number of books.
Space Complexity: For this search method, you don’t need any extra space besides the space for your bookshelf. You’re not making piles of books or using extra boxes to organize them as you search. Therefore, the space complexity is constant, noted as O(1), because no matter how many books you have, the space you use doesn’t change.
So in this case
- Time Complexity: O(n)
- Space Complexity: O(1)
You start from one end and check each book. No extra memory used — just time.
Scenario 2: Using an Alphabetically Sorted Bookshelf (Binary Search)
Time Complexity: Now, imagine if your bookshelf was organized alphabetically. To find your book, you could use a method called binary search. You’d start in the middle, decide if your book is in the left or right half, and then repeat the process with the relevant half. This method significantly reduces the time it takes to find your book, even in the worst case. The time complexity here is O(log n), showing that the time to search grows slower than the number of books.
Space Complexity: However, to maintain an alphabetically sorted bookshelf, you might need extra space. For example, leaving empty spots on each shelf to add new books without reorganizing the whole shelf. The space you need grows with the number of books you have, even if it’s just a little bit for each new book. This introduces a higher space complexity compared to just stacking books any which way.
So in this case
- Time Complexity: O(log n)
- Space Complexity: O(1) or sometimes a bit more (if recursion is used)
Books are sorted alphabetically, so you can go directly to the middle, and keep dividing.
Understanding Through The Example
- Time Complexity: Demonstrates how long it takes to find your book based on how you search.
- Linear Search: Longer time, simpler process (O(n)).
- Binary Search on Sorted Shelf: Faster, but requires initial sorting (O(log n)).
- Space Complexity: Shows how much extra space you need to organize your books.
- Unsorted Shelf: No extra space needed beyond the shelf itself (O(1)).
- Sorted Shelf: Requires extra space for sorting and future additions, impacting how much physical space you use (greater than O(1)).
Balancing Time and Space
Here’s the tricky part — sometimes, faster algorithms use more space, and memory-efficient ones take more time.
It’s like choosing between:
- 📦 A big suitcase (more space, less packing time)
- 🎒 A small backpack (less space, more effort to fit everything)
As developers, we must balance speed vs. memory depending on the problem and device limitations
Important Points to Remember
Property | Time Complexity | Space Complexity |
---|---|---|
Measures | Speed of execution | Memory usage |
Depends on | Input size | Variables, data structures |
Affects | Performance | Resource usage |
Common Notations | O(1), O(n), O(log n), O(n²) | O(1), O(n), O(n²) |
Optimization Goal | Execute faster | Use less memory |
Real-World Analogy
Imagine downloading files:
- Fast download (low time) but takes huge space = High time efficiency, low space efficiency.
- Compressed download (low space) but slower to decompress = Low time, high space efficiency.
Conclusion
To wrap it up — when you write or compare algorithms, always consider:
- Time Complexity – How long does it take?
- Space Complexity – How much memory does it use?
A great algorithm is one that balances both — fast enough to finish on time, and efficient enough to not eat up all the memory.
FAQs
Q1. Which is more important: time or space complexity?
Both are important. But in real-world scenarios, time complexity is often prioritized — unless you’re working with limited memory (like in embedded systems).
Q2. What is O(n)?
It means the time or space increases linearly with the input size. So if input doubles, time/space also doubles.
Q3. Can an algorithm have O(1) time and O(n) space?
Yes. For example, storing all elements in a hash table (fast lookup) takes constant time to search but uses linear space to store data.