Kumaravel Rajan

Interested in Computer Science among other things.

7 minute read

Chapter 1 : Why data structures matter

  1. Data structure operations

    1. Read
    2. Search
    3. Insert
    4. Delete

  2. Array

    1. They are allocated contiguous blocks of memory.
    2. Read - 1 step
    3. Search - n step (where n is the size of the array)
    4. Insert
      1. at end - 1 step
      2. at beginning - n + 1 steps
    5. Delete - n steps

  3. Sets

    1. (simplification:) Same as arrays except that it does not allow duplicate entries.
    2. Read, Search and Delete all same as normal arrays.

    3. Insert operation has diff. time complexity.

      1. Insertion at end: \(n + 1\) steps. n steps for searching if the value we want to insert already exists and 1 step for actual insertion.
      2. Insertion at beginning: \(n + n + 1 = 2n + 1\) steps. n steps to search if value to be inserted already exists. n steps to shift every pre-existing value to the right. 1 step for the actual insertion at the beginning.

Chapter 2: Why algorithms matter

  1. Even though we might settle on a data structure, even then the algorithm we choose to use on this data structure makes a massive difference in efficiency. This is why algorithms matter.

  2. Next data structure - Ordered arrays

    1. What is it?

      It is a classic array except that all elements are at all times ordered in ascending order.

    2. Insertion

      Insertion is more tedious that it was for classic arrays. When we want to insert a value, we first need to determine the index where it must be inserted, then move all elements starting from this index till the array end one step to the right and finally end up inserting the element in the given index.

      Hence, insertion takes \(N + 2\) steps irrespective of index to insert value in. When index is closer to beginning there are fewer comparisons and more shifts. When index is farther away from beginning there are more comparisons and fewer shifts.

      Exception to this rule is that the index to insert is the end of the array. In that case we have N comparisons and 1 step for actual insertion. This makes it \(N + 1\) step.

    3. Searching & binary search

      Having an ordered array enables us to use binary search which is orders of magnitude faster than our traditional linear search. Binary search only works with ordered arrays.

      This is an exapmle of how choosing the right data structure (ordered arrays) enables us to choose an algorithm (binary search) that is much more efficient than any sorting algorithm available to us in a classic array.

      For binary search, though, each time we double the size of the array, we only need to add one more step.

Chapter 3: O Yes! Big O Notation

  1. The key question: If there are N data elements, how many steps will the algorithm take?

  2. O(N) and O(1)

    When an algorithm is O(N) it means when there are N data elements, the algorithm takes N steps.

    1. Algorithm having O(N) complexity is known to have linear time complexity.

      eg: linear search

    2. Algorithm having O(1) complexity means that it has constant time. i.e. Irrespective of the number of data elements (N) the algorithm always takes only 1 step.

      eg: Reading from an array.

  3. The soul of Big O

    How will an algorithm’s performance change as the data increases?

    In other words, it does not just want to tell us how many steps an algorithm takes for N data inputs. It wants to tell us how the number of steps increase as data changes.

    This is why if we have an algorithm that takes 3 steps irrespective of the data size we do not write its complexity as O(3). Instead, we write it as O(1). As mentioned above, Big-O is concerned with the how the number of steps increase as data changes. In this regard, O(3) is the same as O(1).

  4. Big-O and its pessimism

    Big-O can theoretically depict both best-case and worst-case scenarios. For example, in linear search we have the scenario where the searched element is present in index 0 itself. In this best case, linear search becomes O(1). But in the worst case it is as we know O(N).

    But generally, Big-O represents worst-case since this pessimistic approach can help in understanding how inefficient an algorithm can get in the worst-case scenarios and making choices accordingly.

  5. O (log N)

    Refers to algorithms that increase one step every time the data is doubled. In Big-O notation whenever we say O(log N) it is actually \(O(log_2 N)\). We just omit the base 2 for convenience.

    Binary search has O(log N).

  6. Sorting algorithm times from most to least efficient

    Algorithm times arranged
    from Most efficient to least efficient
    O(1)
    O(log N)
    O(N)

Chapter 4: Speeding up your code with Big O

  1. Bubble sort

    In each pass through, the highest unsorted value “bubbles” up to its correct position.

    Bubble sort has \(O(N^2)\) complexity. This means bubble sort has quadratic time.

    Explanation of how bubble sort works is given in wikipedia.

  2. \(O(N^2)\) complexity

    Very often (but not always), when an algorithm nests one loop inside another, the algorithm is \(O(N^2)\).

    
 function hasDuplicateValue(array) { 

     let steps = 0; // count of steps
        
     for(let i = 0; i < array.length; i++) { 
            
         for(let j = 0; j < array.length; j++) {
                
             steps++; // increment number of steps 

             // !!!
             if(i !== j && array[i] === array[j]) { 
                 return true;
             }
         }
     }
     console.log(steps); // print number of steps if no duplicates 
     return false;
 }

    Here, assume we have an array of length N. The outer loop iterates through every element of the array one by one. For every iteration of the outer loop, the inner loop iterates N times. So the statement in the inner loop (the comparison) is executes \(N^2\) times in the worst case. Hence, this code has \(O(N^2)\).

    The criteria here is, how many times is the code in the inner loop (the comparison statements) is executed in the worst case.

    The above code can be optimized to an algorithm that has \(O(N)\) instead of \(O(N^2)\).

    
 function hasDuplicateValue(array) {
     let steps = 0;
     let existingNumbers = [];

     for(let i = 0; i < array.length; i++) {
         steps++;
            
         if(existingNumbers[array[i]] === 1) {
             return true; 
            
         } else {
             existingNumbers[array[i]] = 1;
         }
     }

     console.log(steps); 
     return false;
 }

    Here, we get rid of the inner loop and keep just the outer loop. This means the new code has O(N).

  3. Exercises

Chapter 5: Optimizing Code with and Without Big O

  1. Selection sort

    In each pass-through the lowest element is placed in the current starting position. It takes about half the number of steps bubble sort does. This means selection sort is twice as fast as bubble sort . If bubble sort had \(O(N^2)\) then selection sort should have \(O(N^2/2)\).

    But Big-O notation ignores constants. Therefore, in the Big O notation, Bubble sort and Selection sort both have \(O(N^2)\) runtimes.

    Animation of how selection sort works as given in geeksforgeeks.

  2. Why Big-O ignores constants

    Big-O is concerned with the overarching categories of algorithmic speeds. O(N) and \(O(N^2)\) are completely different categories. O(N) grows linearly as the data increases. \(O(N^2)\) grows exponentially as the data increases.

    Any factor of N in O(N) will at some data size be faster than \(O(N^2)\). Hence, these are differentiated in Big-O.

    But, both O(N) and O(100N) grow linearly as the data increases. This does not interest Big-O. Therefore, both of these algorithms are put under the same category of O(N).

    This is why bubble sort and selection sort are both \(O(N^2)\) even though in reality, selection sort is twice as fast as bubble sort.

Chapter 6: Optimizing for optimistic scenarios

  1. Chapter intent:

    Big-O focuses on worst-case scenarios. But what about those situations which are not worst-case, rather average-case scenarios. In this chapter we will be focusing on such scenarios.

  2. Insertion sort

    Animation of how this works in wikipedia.

    1. Big O Notation only takes into account the highest order of N when we have multiple orders added together.

      i.e. \(O(N^2 + 2N - 2) \implies O(N^2 + N) \implies O(N^2)\)

    2. Time complexity of insertion sort

      In worst case scenarion insertion sort has time complexity of \(O(N^2)\), the same as bubble sort and selection sort.

    3. Efficiency of insertion sort

      • Selection sort: \(O(N^2/2) \implies O(N^2)\)
      • Bubble sort: \(O(N^2) \implies O(N^2)\)
      • Insertion sort: \(O(N^2+2N-2) \implies O(N^2)\)

      Remember these are worst case time complexities. In the average case, insertion sort performs much better.

    4. Insertion sort v/s selection sort

        Best case Average case Worst case
      Selection sort \(N^2/2\) \(N^2/2\) \(N^2/2\)
      Insertion sort N \(N^2/2\) \(N^2\)

Chapter 7: Big O in everyday code

Exercises worked out here.

You May Also Enjoy

Deutsch Notes

less than 1 minute read

My Deutsch B1 exam is on 3 Nov. 2025. I have been preparing for the exam on my own using Telc DaF Kompakt A1-B1 textbook. Here, are the notes on German Gramm...