As we know that a by Designing an Algorithm, a problem can be solved. To perform some tasks based on what the problem is asking. There could be many solutions for a single problem, and each solution results in a unique or similar algorithm. So it becomes very difficult to decide which algorithm to choose from the set of algorithms so that we can get a solution in few steps or finite time. Here, the complexities of an algorithm come into the picture.
The complexity of an algorithm defines the performance of the algorithm in terms of the input size. We consider the complexities of every algorithm and compare them while choosing the most efficient algorithm to solve our problem.
Imagine you have a big box of LEGO blocks and you want to build a house. An algorithm is like the instructions for building that house. Some instructions are quick and easy, while others are long and complicated. In the computer world, we look at how long an algorithm takes (time complexity) and how many LEGO blocks it uses (space complexity).
When we talk about how long an algorithm takes, we’re talking about time complexity. Space complexity is all about how much space, or memory, the algorithm needs. Both are super important because they tell us if our computer can do the job quickly and without running out of space.
Types of Complexity
- Time Complexity
- Space Complexity
1. Time complexity
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.
In simple words, we can see how the algorithm behaves when the input is very low, and gradually, we increase the input size. The input size is generally based on the problem conditions and constraints. The efficiency of a general algorithm is really examined when the input size is considerably high (10^8). General algorithms are the ones that can be used in Frequent like searching or sorting algorithms.
We generally consider the algorithm, which takes a few seconds to solve the problem rather than running infinitely.
Time complexity is like deciding whether to walk, ride a bike, or drive a car to the store. Walking is slow (like a slow algorithm), biking is faster, and driving is fastest. Some algorithms can do their job really fast (driving), while others take longer (walking). For example, finding your favorite toy in a small box is quick. But if you have a huge box filled with toys, it might take a lot longer to find.
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).
While designing an algorithm, we consider minimizing the time as well as space. An algorithm is selected based on the minimal time of execution and sometimes minimal or constant space. In practice, we design an algorithm considering the time complexity and less about the space complexity.
An algorithm that takes less time and less space is considered the optimal and efficient one.
Now, think about how many toys you can fit in your room. If you have too many, you’ll run out of space! In computer terms, some instructions need a lot of memory to work, while others need just a little. It’s like comparing a small toy box to a big garage.
Example
This example will help you to understand more about time and space complexity. Here we are taking an example
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)
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.
Scenario 2: Using an Alphabetically Sorted Bookshelf (Space Complexity)
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.
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
Sometimes, you have to choose between getting something done fast (time) and using less space (memory). It’s like deciding whether to take a big suitcase or a small backpack on a trip. Both choices have pros and cons.
Important Points with Examples
- Real-world Analogy: Imagine you’re tasked with cleaning up your room. You could throw everything into one big box quickly (fast time, high space). Or, you could sort each item into its place, which takes longer but keeps your room tidy (slow time, low space).
- Example: Finding a book in an unsorted pile takes longer and no extra space, while having a sorted shelf takes quick lookup time but more space to set up.
Conclusion
Algorithms help our computers do tasks, from the simplest to the most complex ones. Understanding time and space complexity is like learning to be efficient with both our energy and our room space. The better we get at it, the smarter we can solve problems!