When we talk about computers and programming, we often encounter algorithms. Algorithms are like instructions that help computers perform tasks. However, not all algorithms work the same way. Depending on how much data they need to process, the time they take can vary significantly.
Imagine you have a large library of books, and you want to choose one to read. If you have only three books, you can quickly decide which one to pick. But if there are hundreds of books in the library, it may take you longer to figure out which one you like.
In this article, we will explain how different algorithms work using a simple analogy of choosing books. We will start with the simplest algorithms and move to more complex ones so that you can better understand how and why some algorithms can be faster or slower.
1. O(1) — Constant Complexity
What it means: The execution time does not depend on the size of the data.
Analogy: Imagine you are a huge fan of “1984” by George Orwell, and your books are arranged alphabetically by the author’s last name. You simply take the book you want to read from the shelf.
def get_book(books):
return books[0] # Always returns the first book
2. O(n) — Linear Complexity
What it means: The execution time increases proportionally to the amount of data.
Analogy: Your books are in a random order on the shelf, and you have no idea where anything is. You want to find “All Quiet on the Western Front” by Erich Maria Remarque and start taking books one by one to check which is which. You begin with the first book in line and move on to the next, continuing until you find what you need. The more books you have on the shelf, the more time it will take.
def find_book(books, target):
for book in books:
if book == target:
return book
return None # If the book is not found
3. O(log n) — Logarithmic Complexity
What it means: The execution time grows slowly compared to the increase in the amount of data. If the data is sorted, you can use methods that allow you to reduce the search.
Analogy: Your books are still arranged in alphabetical order, and you want to find “Fahrenheit 451” by Ray Bradbury. Instead of checking each book, you open the middle of the shelf. If the book in the middle starts with “M,” you know your book must be to the left. You then take the middle of the remaining books and continue this way until you find your book. Thus, with each check, you reduce the number of books you need to examine.
def binary_search(books, target):
left, right = 0, len(books) - 1
while left <= right:
mid = (left + right) // 2
if books[mid] == target:
return mid
elif books[mid] < target:
left = mid + 1
else:
right = mid - 1
return None # If the book is not found
4. O(n²) — Quadratic Complexity
What it means: The execution time increases proportionally to the square of the size of the data. This occurs when each data element is compared to every other element.
**Analogy: **You decided to organize your books by title. To do this, you need to compare each book to every other book to determine the correct order. You start with the first book and compare it with all the others. Then you move to the second book and compare it with all the others. If you have 10 books, you’ll need to make 10 × 10 = 100 comparisons to sort them correctly. The more books you have, the longer the process will take.
def bubble_sort(books):
n = len(books)
for i in range(n):
for j in range(0, n-i-1):
if books[j] > books[j+1]:
books[j], books[j+1] = books[j+1], books[j] # Swap places
return books
5. O(2^n) — Exponential Complexity
What it means: The execution time of the task grows very rapidly as the amount of data increases.
Analogy: Imagine you have 3 books, and you want to organize a reading evening. For each book, you can decide whether to read it or not. This means you have several ways to choose books:
• Read nothing.
• Read only the first book.
• Read only the second book.
• Read only the third book.
• Read the first and second books.
• Read the first and third books.
• Read the second and third books.
• Read all three books.
So you have 8 different ways to choose books for reading. If you add a 4th book to your list, the number of ways will grow to 16! The more books you have, the more confusing it becomes.
def get_combinations(books):
result = []
n = len(books)
for i in range(2**n):
combination = []
for j in range(n):
if (i >> j) & 1:
combination.append(books[j])
result.append(combination)
return result
6. O(n!) — Factorial Complexity
What it means: The execution time of the task increases in such a way that it can make the task practically impossible.
Analogy: Imagine you are choosing the order of books to read. You have only 4 books in your list, and you can start with any of them, then choose any of the remaining ones, then from the remaining two, and finally read the last one.
Since you can read these books in any order, for 4 books, you have many options:
- Book A, then Book B, then Book C, then Book D.
- Book A, then Book B, then Book D, then Book C.
- Book A, then Book C, then Book B, then Book D.
- And so on. If you add another book to your list, the number of possible reading orders will increase even more, and this number grows very rapidly! For example, for 4 books, there are 24 different orders (that’s 4!). If you add a 5th book, it becomes 120 options. The more books you have, the harder it is to decide how to read them because the options become too many!
from itertools import permutations
def get_reading_orders(books):
return list(permutations(books))
Understanding algorithm complexity helps us choose the right approach to solving problems. When we know how fast or slow an algorithm works, we can organize our actions more effectively — whether it’s selecting a book to read or developing a business process.
If you’d like to receive more content like this, including insights on AI, machine learning, and technology trends, subscribe to our newsletter at www.terekhindt.com.
Top comments (0)