Home › DSA › Foundations

Analyzing Simple Algorithms

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

java

class Solution {
    public int find_max(int[] numbers) { 
        int max_num = numbers[0];
        // Finding the maximum number in array
        for (int num : numbers) {
            if (num > max_num) {
                max_num = num;
            }
        }
        return max_num;
    }

    public static void main(String[] args) {
        int[] numbers = {3, 7, 2, 9, 5}; // Example array

        Solution solution = new Solution();
        int maxValue = solution.find_max(numbers);
        
        System.out.println("Maximum number: " + maxValue);
    }
}

Step-by-Step Analysis

Initialization: max_num = numbers[0]
- This assignment is constant and takes time.
Loop through the List: for num in numbers
- The loop runs once for each element in the list, making it 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 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 overall.

Total Time Complexity

Adding all these steps together, we get:

Initialization:
Loop (including conditional check and assignment):

Since , the total time complexity of the find_max algorithm is .

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

java

class Solution {

  public int[] insertion_sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
      int key = arr[i];
      int j = i - 1;

      // Shift elements to the right to create space for key
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }

      // Insert key at the correct position
      arr[j + 1] = key;
    }
    return arr; // Returning the sorted array
  }

  public static void main(String[] args) {
    int[] arr = { 5, 3, 8, 1, 2 }; // Example array

    Solution solution = new Solution();
    int[] sortedArr = solution.insertion_sort(arr);

    // Printing sorted array
    System.out.print("Sorted array: ");
    for (int num : sortedArr) {
      System.out.print(num + " ");
    }
  }
}

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 .
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 comparisons.
- This sum simplifies to approximately , giving us a time complexity of .

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

🤖 Don't fully get this? Learn it with Claude

Stuck on Analyzing Simple Algorithms? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Analyzing Simple Algorithms** (DSA) and want to truly understand it. Explain Analyzing Simple Algorithms from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Analyzing Simple Algorithms** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Analyzing Simple Algorithms** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Analyzing Simple Algorithms** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Analyzing Control Structures Best, Worst, and Average Cases →