Analyzing Simple Algorithms

Grokking Algorithm Complexity and Big-O

Ask Author

Back to course home

0% completed

Vote For New Content

Analyzing Simple Algorithms

Table of Contents

Contents are not accessible

In this lesson, we’ll practice analyzing time complexity using two basic algorithms: finding the maximum element in a list and Insertion Sort. Both examples will reinforce the process of breaking down an algorithm and identifying the time complexity.

Example 1: Finding the Maximum Element in a List

Let’s start with a simple algorithm to find the maximum element in a list of n numbers.

Algorithm Code

Python3

. . . .

Step-by-Step Analysis

Initialization: max_num = numbers[0]
- This assignment is constant and takes $O(1)$ time.
Loop through the List: for num in numbers
- The loop runs once for each element in the list, making it $O(n)$ because we’re visiting every element once.
Conditional Check: if num > max_num
- Inside the loop, the if statement checks each element. Since this check is executed in each iteration, it contributes $O(n)$ to the time complexity.
Assignment Inside Loop: max_num = num
- The assignment only happens when the condition is true. However, it’s still part of the loop, so we consider its complexity as $O(n)$ overall.

Total Time Complexity

Adding all these steps together, we get:

Initialization: $O(1)$
Loop (including conditional check and assignment): $O(n)$

Since $O(1) + O(n) = O(n)$ , the total time complexity of the find_max algorithm is $O(n)$ .

Example 2: Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It’s useful for small or nearly sorted data but can be inefficient for larger lists.

Algorithm Code

Python3

. . . .

Step-by-Step Analysis

Let’s break down each part of the code and analyze its time complexity.

Outer Loop: for i in range(1, len(arr))
- This loop runs from the second element (index 1) to the last element of arr, so it iterates n - 1 times (where n is the length of the array).
- The outer loop contributes a time complexity of $O(n)$ .
Inner Loop: while j >= 0 and arr[j] > key
- The inner while loop compares arr[j] to key and shifts elements if they are larger than key.
- In the worst case, the while loop can run i times for each i in the outer loop, especially if the list is in reverse order.
- On average, for each element, it runs half of i times, resulting in time complexity contributions for each outer loop iteration.
Total Time Complexity

To understand the full time complexity, let’s examine different cases:
- When the array is in reverse order, each element is compared with all the previous elements. This results in a maximum of $1 + 2 + 3 + ... + (n - 1)$ comparisons.
- This sum simplifies to approximately $\frac{n(n - 1)}{2}$ , giving us a time complexity of $O(n^2)$ .

In the next lesson, Best, Worst, and Average Cases, we’ll explore how different inputs affect the performance of algorithms like insertion sort.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible