Algorithms the Gentleman Way

Big O Notation

"How code slows as data grows"

  1. Performance of an algorithm depends on the amount of data it is given.
  2. Number of steps needed to complete. Some machines run algorithms faster than others so we just take the number of steps needed.
  3. Ignore smaller operations, constants. O(N + 1) -> O(N) where N represents the amount of data.
function sum(n: number): number {
  const sum = 0;

  for(let i = 0; i < n; i++) {
    sum += i;
  }

  return sum;
}

// if n equals 10, then O(N) is 10 steps, if in equals 100, then O(N) is 100 steps

Here we can see that O(N) is linear which means that the amount of steps depends on the number of data we are given.

function sayHi(n: string):  string{
  return `Hi ${n}`
}

// if n equals 10, then O(1) is 3 step... 3 ? YES 3 steps

// 1 - Create new string object to store the result (allocating memory for the new string)
// 2 - Concatenate the 'Hi' string with the result.
// 3 - Return the concatenated string.

But now we have O(1) as the amount of steps does not depend on the amount of data we are given, it will always be 1.

Needed previous knowledge

  • The 'Log' of a number is the power to which the base must be raised to produce that number. For example, the log base 2 of 8 is 3 because 2^3 = 8.

  • 'Linear' means that the number of steps grows linearly with the amount of data.

  • The 'Quadratic' of a number is the square of that number. For example, the quadratic of 3 is 9 because 3^2 = 9.

  • 'Exponential' of a number is the power of the base raised to that number. For example, the exponential of 2 to the power of 3 is 8 because 2^3 = 8.

  • 'Factorial' of a number is the product of all positive integers less than or equal to that number. For example, the factorial of 3 is 6 because 3!!) - Factorial time - The number of steps grows factorially (brute force algorithms, those which try all possible solutions)


Example with N equal to 1000:

```bash
- O(1) - 1 step
- O(log N) - 10 steps
- O(N) - 1000 steps, a thousand steps
- O(N log N) - 10000 steps, a ten thousand steps
- O(N^2) - 1000000 steps, a million steps
- O(2^N) - 2^1000 steps
- O(N!) - 1000! steps, factorial of 1000

The main idea is that we want to avoid exponential and factorial time algorithms as they grow very fast and are not efficient at all, UNLESS we are sure that the amount of data we are given is very small as it can actually be faster than other algorithms.

Letter grade for Big O Notation, from best to worst, taking in consideration we are using a big dataset of data:

- O(1) - Constant time - A
- O(log N) - Logarithmic time - B
- O(N) - Linear time - C
- O(N log N) - Linearithmic time - D
- O(N^2) - Quadratic time - F
- O(2^N) - Exponential time - F
- O(N!) - Factorial time - F

Examples using code

O(1) - Constant time

  function sayHi(n: string):  string{
    return `Hi ${n}`
  }

Here's why it's O(1):

  • The algorithm performs a constant amount of work, regardless of the size of the input.
  • The number of steps needed to complete the algorithm does not depend on the input size.

Therefore, the time complexity of the algorithm is O(1) in all cases.

O(log N) - Logarithmic time

  // having the following array that represents the numbers from 0 to 9 in order
  const arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

  // we want to find the index of a number in the sorted array
  function binarySearch(arr: number[], target: number): number {
    // initialize left and right pointers
    let left = 0;
    let right = arr.length - 1;

    // while left is less or equal to right we keep searching for the target
    while (left <= right) {
      // get the middle of the array to compare with the target
        // we iterate using the middle of the array to find the target because we know the array is sorted and we can discard half of the array in each iteration
      const mid = Math.floor((left + right) / 2); // middle index
      const midValue = arr[mid]; // middle value

      // if the middle value is the target, return the index
      if (midValue === target) {
        return mid;
      }

      // if the middle value is less than the target, we search the right side of the array by updating the left pointer
      if (midValue < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return -1; // target not found
  }

In binary search, the algorithm continually divides the search interval in half until the target element is found or the search interval becomes empty. With each iteration, the algorithm discards half of the search space based on a comparison with the middle element of the current interval.

Here's why it's O(log N):

  • In each iteration of the while loop, the search space is halved.
  • This halving process continues until the search space is reduced to a single element or the target is found.
  • Since the search space is halved with each iteration, the number of iterations required to reach the target element grows logarithmically with the size of the input array.

Thus, the time complexity of binary search is O(log N) on average.

O(N) - Linear time

  function sum(n: number): number {
    const sum = 0;
    for(let i = 0; i < n; i++) {
      sum += i;
    }
    return sum;
  }

Here's why it's O(N):

  • The algorithm iterates over the input array once, performing a constant amount of work for each element.
  • The number of iterations is directly proportional to the size of the input array.
  • As the input size increases, the number of steps needed to complete the algorithm grows linearly.

Therefore, the time complexity of the algorithm is O(N) in the worst-case scenario.

O(N log N) - Linearithmic time

  // having the following array
  const arr = [5, 3, 8, 4, 2, 1, 9, 7, 6];

  // we want to sort the array using the quick sort algorithm
  function quickSort(arr: number[]): number[] {
    // first we check if the array has only one element or no elements
    if (arr.length <= 1) {
      return arr;
    }

    // we get the pivot as the last element of the array, the pivot is the element we are going to compare the rest of the elements with
    const pivot = arr[arr.length - 1];

    // we create two arrays, one for the elements less than the pivot and another for the elements greater than the pivot
    const left = [];
    const right = [];

    // we iterate through the array and compare each element with the pivot
    for (let i = 0; i < arr.length - 1; i++) {
      // if the element is less than the pivot, we add it to the left array
      if (arr[i] < pivot) {
        left.push(arr[i]);
      } else {
        // if the element is greater than the pivot, we add it to the right array
        right.push(arr[i]);
      }
    }

    // we recursively call the quickSort function on the left and right arrays and concatenate the results
    return [...quickSort(left), pivot, ...quickSort(right)];
  }

Here's why it's O(N log N):

  • The algorithm partitions the array into two subarrays based on a pivot element and recursively sorts these subarrays.
  • Each partitioning step involves iterating over the entire array once, which takes O(N) time. However, the array is typically divided in a way that the size of the subarrays reduces with each recursive call. This results in a time complexity of O(N log N) on average.

O(N^2) - Quadratic time

  // having the following array
  const arr = [5, 3, 8, 4, 2, 1, 9, 7, 6];

  // we want to sort the array using the bubble sort algorithm
  function bubbleSort(arr: number[]): number[] {

    // we iterate through the array
    for (let i = 0; i < arr.length; i++) {

      // we iterate through the array again
      for (let j = 0; j < arr.length - 1; j++) {

        // we compare adjacent elements and swap them if they are in the wrong order
        if (arr[j] > arr[j + 1]) {
          
          // we swap the elements
          const temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
    return arr;
  }

Here's why it's O(N^2):

  • Bubble sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.
  • In the worst-case scenario, where the array is in reverse sorted order, bubble sort will need to make N passes through the array, each pass requiring N-1 comparisons and swaps.
  • This results in a total of N * (N-1) comparisons and swaps, which simplifies to O(N^2) in terms of time complexity.

O(2^N) - Exponential time

  // we want to calculate the nth Fibonacci number using a recursive algorithm
  function fibonacci(n: number): number {

    // we check if n is 0 or 1 as the base case of the recursion because the Fibonacci sequence starts with 0 and 1
    if (n <= 1) {
      return n;
    }

    // we recursively call the fibonacci function to calculate the nth Fibonacci number
    return fibonacci(n - 1) + fibonacci(n - 2);
  }

Here's why it's O(2^N):

  • In each recursive call to the fibonacci function, two additional recursive calls are made with n - 1 and n - 2 as arguments.
  • This leads to an exponential growth in the number of recursive calls as n increases.
  • Each level of recursion branches into two recursive calls, resulting in a binary tree-like structure of recursive calls.
  • The number of function calls doubles with each level of recursion, leading to a total of 2^N function calls when calculating the nth Fibonacci number.

Therefore, the time complexity of the algorithm is O(2^N) in the worst-case scenario.

O(N!) - Factorial time

  // having the following array
  const arr = [1, 2, 3];

  // we want to generate all permutations of a given array using a recursive algorithm
  function permute(arr: number[]): number[][] {
    // base case: if the array has only one element, return it as a single permutation
    if (arr.length <= 1) {
      return [arr];
    }

    // initialize an empty array to store permutations
    const result: number[][] = [];

    // iterate over each element in the array
    for (let i = 0; i < arr.length; i++) {
      // generate all permutations of the array excluding the current element
      const rest = arr.slice(0, i).concat(arr.slice(i + 1));
      const permutations = permute(rest);

      // add the current element to the beginning of each permutation
      for (const perm of permutations) {
        result.push([arr[i], ...perm]);
      }
    }
    return result;
  }

Here's why it's O(N!):

  • In each recursive call to the permute function, the algorithm generates permutations by selecting each element of the array as the first element and then recursively generating permutations of the remaining elements.
  • The number of permutations grows factorially with the size of the input array.
  • For each element in the array, there are (N-1)! permutations of the remaining elements, where N is the number of elements in the array.
  • Therefore, the total number of permutations is N * (N-1) * (N-2) * ... * 1, which is N factorial (N!).

Hence, the time complexity of the algorithm is O(N!) in the worst-case scenario.

Worst-case, Best-case, and Average-case Complexity

  • The worst-case time complexity represents the maximum number of steps an algorithm takes to complete for a given input size. It provides an upper bound on the algorithm's performance. It is the most commonly used measure of time complexity in job interviews.

  • The best-case time complexity represents the minimum number of steps an algorithm takes to complete for a given input size. It provides a lower bound on the algorithm's performance. It is less informative than the worst-case complexity and is rarely used in practice.

  • The average-case time complexity represents the expected number of steps an algorithm takes to complete for a given input size, averaged over all possible inputs. It provides a more realistic estimate of an algorithm's performance than the worst-case complexity. However, calculating the average-case complexity can be challenging and is often avoided in favor of the worst-case complexity.

Space complexity

The space complexity of an algorithm is a measure of the amount of memory it requires to run as a function of the input size. It is typically expressed in terms of the maximum amount of memory used by the algorithm at any point during its execution.

It is important to distinguish between time complexity and space complexity, as an algorithm with good time complexity may have poor space complexity, and vice versa. For example, a recursive algorithm with exponential time complexity may also have exponential space complexity due to the recursive calls consuming memory.

But something to have in mind is that space complexity is not as important as time complexity, as memory is usually cheaper than processing power and in real life scenarios, we usually skip the space complexity analysis and focus on time complexity.

Imagine you're at a traditional Argentine barbecue, known as an "asado." You've got limited space on the grill (similar to limited memory in computing), and you want to optimize how much meat you can cook at once.

Now, let's compare the meat (or "carne") to the data in an algorithm. When you're cooking, you have to consider how much space each cut of meat takes up on the grill. Similarly, in computing, algorithms have to consider how much memory space they need to store and process data.

But here's the thing: at an asado, the most important factor is usually how quickly you can cook the meat and serve it to your guests. Similarly, in computing, the time it takes for an algorithm to run (time complexity) is often the most critical factor for performance.

So, while it's essential to be mindful of how much space (or "espacio") your algorithm uses, it's usually more exciting to focus on how efficiently it can solve a problem in terms of time.

Of course, in some situations, like if you're grilling on a tiny balcony or cooking for a huge crowd, space becomes more of a concern. Similarly, in computing, if you're working with limited memory resources or on a device with strict memory constraints, you'll need to pay closer attention to space complexity.

But overall, just like at an Argentine barbecue, the balance between time and space complexity is key to creating a delicious (or efficient) outcome!

However, let's talk about how you calculate the space complexity, or "cuánto espacio ocupas" in the case of our barbecue analogy. Just as you'd assess how much space each cut of meat takes up on the grill, in computing, you need to consider how much memory each data structure or variable in your algorithm consumes.

Here's a basic approach to calculate space complexity:

  1. Identify the Variables and Data Structures: Look at the algorithm and identify all the variables and data structures it uses. These could be arrays, objects, or other types of variables.

  2. Determine the Space Used by Each Variable: For each variable or data structure, determine how much space it occupies in memory. For example, an array of integers will take up space proportional to the number of elements multiplied by the size of each integer.

  3. Add Up the Space: Once you've determined the space used by each variable, add them all up to get the total space used by the algorithm.

  4. Consider Auxiliary Space: Don't forget to account for any additional space used by auxiliary data structures or function calls. For example, if your algorithm uses recursion, you'll need to consider the space used by the call stack.

  5. Express Space Complexity: Finally, express the space complexity using Big O notation, just like you do with time complexity. For example, if the space used grows linearly with the size of the input, you'd express it as O(N). If it grows quadratically, you'd express it as O(N^2), and so on.

So, just as you carefully manage the space on your grill to fit as much meat as possible without overcrowding, in computing, you want to optimize the use of memory to efficiently store and process data. And just like finding the perfect balance of meat and space at an Argentine barbecue, finding the right balance of space complexity in your algorithm is key to creating a delicious (or efficient) outcome!

Example Time !!!

Let's use a simple algorithm to find the sum of elements in an array as an example for calculating space complexity.

function sumArray(arr: number[]): number {
    let sum = 0;  // Space used by the sum variable: O(1)

    for (let num of arr) {  // Space used by the loop variable: O(1)
        sum += num;  // Space used by temporary variable: O(1)
    }

    return sum;  // Space used by the return value: O(1)
}

In this example:

  1. We have one variable sum to store the sum of elements, which occupies a constant amount of space, denoted as O(1).
  2. We have a loop variable num that iterates through each element of the array. It also occupies a constant amount of space, O(1).
  3. Within the loop, we have a temporary variable to store the sum of each element with sum, which again occupies a constant amount of space, O(1).
  4. The return value of the function is the sum, which also occupies a constant amount of space, O(1).

Since each variable and data structure in this algorithm occupies a constant amount of space, the overall space complexity of this algorithm is O(1).

In summary, the space complexity of this algorithm is constant, regardless of the size of the input array.

Now let's consider an example where we create a new array to store the cumulative sum of elements from the input array. Here's the algorithm:

function cumulativeSum(arr: number[]): number[] {
    const result = []; // Space used by the result array: O(N), where N is the size of the input array
    let sum = 0;  // Space used by the sum variable: O(1)
    for (let num of arr) {  // Space used by the loop variable: O(1)
        sum += num;  // Space used by temporary variable: O(1)
        result.push(sum);  // Space used by the new element in the result array: O(1), but executed N times
    }
    return result;  // Space used by the return value (the result array): O(N)
}

In this example:

  1. We have a variable result to store the cumulative sum of elements, which grows linearly with the size of the input array arr. Each element added to result contributes to the space complexity. Therefore, the space used by result is O(N), where N is the size of the input array.
  2. We have a loop variable num that iterates through each element of the input array arr, which occupies a constant amount of space, O(1).
  3. Within the loop, we have a temporary variable sum to store the cumulative sum of elements, which occupies a constant amount of space, O(1).
  4. Inside the loop, we add a new element to the result array for each element in the input array. Each push operation adds an element to the array, so it also contributes to the space complexity. However, since it's executed N times (where N is the size of the input array), the space used by the push operations is O(N).
  5. The return value of the function is the result array, which occupies O(N) space.

Overall, the space complexity of this algorithm is O(N), where N is the size of the input array. This is because the space used by the result array grows linearly with the size of the input.

Arrays

When we talk about arrays, we usually think of ordered collections of elements, right? But in JavaScript, arrays are actually objects. So, what's a real array, you might ask? Well, a true array is a contiguous block of memory where each element takes up the same amount of space.

In a real array, accessing an element is super quick—it's a constant time operation, meaning it takes the same amount of time no matter how big the array is. Why? Because you can calculate exactly where each element is in memory.

Now, let's contrast that with JavaScript arrays. They're implemented as objects, where the indexes are the keys. So, when you access an element in a JavaScript array, you're actually accessing a property of an object. This means accessing elements isn't as snappy—it's a linear time operation because the JavaScript engine has to search through the object keys to find the right one.

To find the memory location of an element in a real array, you use a simple formula:

const index = base_address + offset * size_of_element;

Here, the index is what we usually call the index, but it's more like an offset. The base_address is the starting point of the array in memory, and size_of_element is, well, the size of each element.

With this formula, every time you search for an element, you're performing a constant time operation because it doesn't matter how big the array is—the math stays the same.

Now, let's illustrate this with some code:

// Let's create a new array with 5 elements
const a = [1, 2, 3, 4, 5];

// Calculate the total space the array occupies in memory
const totalSpace = array.length * 4; // assuming each element occupies 4 bytes

// Choose an index
const index = 3;

// Calculate the memory location of the element
const sizeOfEachElement = 4; // each element occupies 4 bytes
const baseAddress = array; // the reference to the array itself
const offset = index * sizeOfEachElement;
const memoryLocation = baseAddress + offset;

// Access the element at the calculated memory location
const elementAtIndex = memoryLocation;

console.log("Value at index", index, "is:", elementAtIndex); // Value at index 3 is: 4

In this example, we're simulating how a real array works under the hood. We calculate the memory location of an element using the index, and then we access that memory location to get the element.

Now, let's visualize this with Node.js, where we can peek into what's happening in memory:

// Create a new array buffer in Node.js
const buffer = new ArrayBuffer(16); // 16 bytes of memory

// Check the size of the buffer (in bytes)
console.log("buffer.byteLength: " + buffer.byteLength); // Output: buffer.byteLength: 16

// Now let's create a new Int8Array, a typed array of 8-bit signed integers
const int8Array = new Int8Array(buffer);

// Log the contents of the Int8Array (all zeros initially)
console.log(int8Array); // Output: Int8Array(16) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

// Each element in the Int8Array represents a single byte in the buffer

// Now let's change the value of the first element of the array to 1
int8Array[0] = 1;

// Log the contents of the Int8Array and buffer again
console.log(int8Array); // Output: Int8Array(16) [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
console.log(buffer); // Notice how the underlying buffer is also modified (first byte becomes 1)
// Output: Buffer after change: ArrayBuffer { [Uint8Contents]: <01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00> }

// TypedArrays provide a different view of the same memory

// Now let's create a 16-bit signed integer array (uses 2 bytes per element)
const int16Array = new Int16Array(buffer);

// Log the contents of the Int16Array (initial values based on buffer)
console.log(int16Array); // Output: Int16Array(8) [1, 0, 0, 0, 0, 0, 0, 0]

// The Int16Array has fewer elements because it uses more bytes per element, 2 bytes

// Again, let's change a value (third element) and see the effects
int16Array[2] = 4000;

// Log the contents of all three arrays and the buffer
console.log(int16Array); // Output: Int16Array(8) [1, 0, 4000, 0, 0, 0, 0, 0]
console.log(buffer); // Notice how multiple bytes in the buffer are modified (5th and 6th bytes)
// Output: ArrayBuffer { [Uint8Contents]: <01 00 00 00 a0 0f 00 00 00 00 00 00 00 00 00 00> } (contents are modified, e.g., 5th byte might be 0x0f)
console.log(int8Array); // The view of the Int8Array is also affected  (5th and 6th bytes change)
// Output: Int8Array(16) [1, 0, 0, 0, -96, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (5th byte is -96, 6th byte is 15, being shown in decimal)

// Now let's create a 32-bit signed integer array (uses 4 bytes per element)
const int

32Array = new Int32Array(buffer);

// Log the contents of the Int32Array (initial values based on buffer)
console.log(int32Array); // Output: Int32Array(4) [1, 4000, 0, 0]

// Even fewer elements due to the larger size of each element, 4 bytes

// Let's change the value and observe the effects
int32Array[2] = 100000;

// Log the contents of all three arrays and the buffer
console.log(int32Array); // Output: Int32Array(4) [1, 4000, 100000, 0]
console.log(buffer); // ArrayBuffer { [Uint8Contents]: <01 00 00 00 a0 0f 00 00 10 27 00 00 00 00 00 00> } even more bytes in the buffer are modified (9th, 10th, 11th, 12th)
console.log(int16Array); // Int16Array(8) [1, 0, 4000, 0, 10000, 0, 0, 0] (4th element is now 10000)
console.log(int8Array); // Int8Array(16) [1, 0, 0, 0, -96, 15, 0, 0, 16, 39, 0, 0, 0, 0, 0, 0] (9th, 10th, 11th, 12th bytes are now 16, 39)

In this Node.js example, we're creating a buffer of 16 bytes, which is like a block of memory. Then, we create different typed arrays to view this memory differently—as arrays of different types of integers. Modifying one of these arrays also changes the underlying buffer, showing how they're different views of the same memory.

Now, let's circle back to why we're seeing decimals. We'll need to understand two's complement representation first.

So, two's complement is like the magic trick we use in computing to handle both positive and negative numbers using the same binary system. Picture this: in our binary numbers, the first digit from the left (the big boss, you know?) decides if the number is positive or negative. If it's 0, it's positive, and if it's 1, it's negative.

Now, for the positive numbers, it's easy peasy. You just write them down in binary, as usual. For example, number 3 in 8-bit binary is 00000011. No problem there, right?

But when it comes to negative numbers, we need a trick. We take the positive number's binary representation, flip all the bits (0s become 1s and 1s become 0s), and then add 1 to the result. This gives us the two's complement of the negative number. Let's say we want to represent -3. First, we start with 3's binary representation, which is 00000011. Then, we flip all the bits to get 11111100, and finally, we add 1 to get 11111101. That's the two's complement of -3 in 8-bit binary.

Now, why do we do all this? Well, it's because in computing, we like things to be tidy and consistent. With two's complement, we can use the same rules for adding and subtracting both positive and negative numbers, without needing to worry about special cases. It keeps our math nice and clean, just like sipping on yerba mate on a sunny day in Buenos Aires.

Now we can see why we are seeing decimals !

When working with 8 bits, the values are being represented in decimal, as the range of an 8-bit signed integer is -128 to 127. If the value overflows, it wraps around the range:

When you're dealing with 8 bits, the values are shown in decimal because, you know, an 8-bit signed integer can only hold numbers from -128 to 127. It's like having a limited space in a crowded bus—you can only fit so many people!

Now, imagine you're trying to squeeze in the number 4000. In binary, that's 111110100000. But here's the thing: our bus only goes up to 127. So, when you try to cram 4000 in there, it's like trying to fit a football team into a tiny car—it's just not gonna happen.

Now, when you try to jam 4000 into our 8-bit bus, it overflows. But instead of causing chaos, it does something pretty neat: it wraps around. You see, the bus route starts again from the beginning, like a never-ending loop.

This "wrapping around" is where things get interesting. The leftmost bit, the big boss of the number, flips its sign. So, instead of being positive, it becomes negative. It's like turning the bus around and going in the opposite direction!

Now, we use our previous trick called two's complement to figure out the new number. First, we flip all the bits of 111110100000 to get 000001011111. Then, we add 1 to this flipped number, giving us 000001100000.

And voilà! That binary number 000001100000 represents -96 in decimal. So, even though you tried to squeeze in 4000, our little bus handles it like a champ and tells you it's -96. That's the magic of overflow and wrap-around in an 8-bit world!

How to think?

When you're up to your eyeballs in code, understanding the concepts and applying them to crack those problems is the name of the game. My advice? Pour your heart and soul into commenting your code, explaining each step inside the method, and THEN dive into implementation.

That way, you'll know what needs doing and just need to figure out how to pull it off.

Example:

function sumArray(arr: number[]): number {
		// Initialize the sum variable to store the sum of elements
		let sum = 0;  // O(1)

		// Iterate over each element in the array
		for (let num of arr) {  // O(N)
				// Add the current element to the sum
				sum += num;  // O(1)
		}

		// Return the final sum
		return sum;  // O(1)
}

Linear Search

It's the bread and butter of algorithms, but do you really know how it struts its stuff?

Here's the scoop: we're sashaying through each element of a collection, asking if the element we're hunting down is the one staring us in the face. The JavaScript bigwig that uses this algorithm? The indexOf method, baby.

function indexOf(arr: number[], target: number): number {
	// Iterate over each element in the array
	for (let i = 0; i < arr.length; i++) {

		// Check if the current element is equal to the target
		if (arr[i] === target) {

			// If it is, return the index of the element
			return i;
		}
	}

	// If the target is nowhere to be found, return -1
	return -1;
}

So... what's the worst-case scenario here that'll give us the Big O Notation? That we come up empty-handed or that the element we're after is lounging at the end of the array, making this algorithm O(N). As N gets bigger, so does the complexity - it's like watching your waistline after devouring a mountain of alfajores.

Binary Search

Now, this bad boy right here is the cream of the crop, the bee's knees, and one of the heavy hitters in professional interviews and coding showdowns. Let's unpack when and how to unleash its power:

The name of the game? Divide and conquer, baby! Instead of playing tag with each element of the array, we slice that sucker in half and ask, "Hey, are you on the left or right?" Then, we keep slicing and dicing until we've nabbed our elusive target.

function binarySearch(arr: number[], target: number): number {
	// Initialize the left and right pointers
	// left starts at the beginning of the array
	// right starts at the end of the array
	let left = 0;
	let right = arr.length - 1;

	// Keep on truckin' as long as the left pointer is less than or equal to the right pointer
	while (left <= right) {
		// Calculate the middle index of the current search space
		const mid = Math.floor((left + right) / 2);

		// Check if the middle element is the target
		if (arr[mid] === target) {

			// If it is, return the index of the element
			return mid;
		} else if (arr[mid] < target) {

			// If the middle element is less than the target, swing right
			left = mid + 1;
		} else {

			// If the middle element is greater than the target, veer left
			right = mid - 1;
		}
	}
}

And whit this example you will see, clear as the light that guide us in the darkest nights that I'm not lying:

// we need to find the index of the target number inside an array of 1024 elements

1024 / 2 = 512 // we halve it and see that the target number is in the right half
512 / 2 = 256 // we halve it again and see that the target number is in the right half
256 / 2 = 128 // we halve it again and see that the target number is in the right half
128 / 2 = 64 // we halve it again and see that the target number is in the right half
64 / 2 = 32 // we halve it again and see that the target number is in the right half
32 / 2 = 16 // we halve it again and see that the target number is in the right half
16 / 2 = 8 // we halve it again and see that the target number is in the right half
8 / 2 = 4 // we halve it again and see that the target number is in the right half
4 / 2 = 2 // we halve it again and see that the target number is in the right half
2 / 2 = 1 // we halve it again and see that the target number is in the right half
1 / 2 = 0.5 // we can't halve it anymore, so we stop

// here comes the magic, if we count the number of steps we have a total of 10 steps to find the target number
// do you know what is the logarithm of 1024 in base 2? it's 10 !!
log2(1024) = 10

Exercise of the Crystal Ball

The crystal ball problem is a classic mathematical issue that is often tackled in programming interviews. It involves finding the position where two crystal balls meet and shatter when dropped from a certain height. The key here isn’t to know about the crystal balls, their falling from a height, or any other detail; we need to grasp the fundamentals and generalize to make it applicable in any scenario. If we can accomplish this, we can represent the height as an array of n elements, where 0 is the start of the fall, n is the maximum height, and the index is the place where the balls collide.

// f = not found, t = found or previously encountered
const height = [f, f, f, f, f, f, t, t, t, t, t];
//             start              collision        end of the fall

Solution

Let’s review the tools we already have to solve this problem:

  • Arrays: Arrays are data structures containing a set of elements of the same type. In this case, the heights of the balls.
  • Loop: Loop is a control structure that allows repeating a section of code a number of times. In this case, the number of repetitions is the number of elements in the array.
  • If: If is a control structure that allows executing a section of code if a condition is true. In this scenario, the condition is whether the element in the array is true or false.
  • Linear Search: Linear Search is a searching technique in which an element is searched sequentially in an array by checking each position of the array consecutively.
  • Binary Search: Binary Search is a searching technique in which an element is searched in an array by dividing the array into two parts and searching for the element in the part that most fits what we are looking for and so forth.
// Linear search
const height = [f, f, f, f, f, f, t, t, t, t, t];

function findCrystalBall(height: number[]): number {
  for (let i = 0; i < height.length; i++) {
    if (height[i] === true) {
      return i;
    }
  }

  return -1;
}

The issue with this solution is that it cannot be optimized to work in every case, as linear search checks each position of the array consecutively, meaning if the array has many elements, the execution time will be very long.

So, let’s look for a more efficient solution.

// Binary search
function findCrystalBall(height: number[]): number {
  let start = 0;
  let end = height.length - 1;

  while (start <= end) {
    const index = Math.floor((start + end) / 2);

    if (height[index] === true) {
      return index;
    } else if (height[index] === false) {
      start = index + 1;
    } else {
      end = index - 1;
    }
  }

  return -1;
}

Does it work? The truth is, no! Because we're not finding the exact moment when the balls meet. Instead, we're returning the first true we find, rather than the very first one. Additionally, if we consider the condition that once a ball breaks, it cannot be used again, the execution time remains linear with the size of the array. In the worst case, we will search through half the height, and if we find a true, we will need to go back to the previous position and determine the exact breaking point, which still results in O(N) complexity.

So let's combine everything we've learned to implement a more incredible and much more efficient solution:

1- We will reduce the size of the section cut so that instead of half the array, it is the square root of N, which significantly reduces the execution time.

2- Once we find the first true, we will return to the point where the section cut begins (SQRT(N)) and search for the first true found linearly.

function findCrystalBall(height: number[]): number {
  const N = height.length;
  const SQRT = Math.floor(Math.sqrt(N));

  // Now we will reduce the size of the section cut so that instead of half the array, it is the square root of N
  // and we traverse it linearly, the square root of N at a time
  let i = SQRT;

  for (; i < N; i += SQRT) {
    if (height[i] === true) {
      break;
    }
  }

  i -= SQRT;

  for (let j = 0; j < SQRT && i < N; i++, j++) {
    if (height[i] === true) {
      return i;
    }
  }

  return -1;
}

// Binary search
function findCrystalBall(height: number[]): number {
  let start = 0;
  let end = height.length - 1;

  while (start <= end

) {
    const index = Math.floor((start + end) / 2);

    // check if the value at the mid position is 'true' and
    // if it is the first 'true' in the array (the previous element must be 'false' if index is not 0)
    if (height[index] === true)
      if (index === 0 || height[index - 1] === false) return index;
      else end = index - 1;
    else start = index + 1;
  }

  return -1;
}

While both solutions work and seem effective, binary search is more efficient!

  • N = 1000 steps
  • SQRT(N) = 100 steps
  • log2(N) = 10 steps

crystal-ball-algorithms

Bubble Sort

Sorting is one of the most common tasks we perform daily as programmers, BUT many people don't really understand what's happening behind the scenes and rely on the famous "magic" functions that are part of every programming language.

Believe it or not, sorting is one of the easiest things we can do! And the best part is that it's also one of the shortest algorithms to write.

The main idea of bubble sort is that it iterates over an array, comparing each element with the next one. If the current element is greater than the next, they are swapped. What's important to note is that at the end of the first iteration, the largest element will have bubbled up to the end of the array. This allows us to iterate through the array again to continue sorting the remaining elements more efficiently, as we can exclude the last element from the previous iteration and so reduce the number of elements to be considered with each pass until the array is sorted.

let unsortedArray = [3, 1, 4, 8, 2];

// first iteration
// compare the first with the second and swap them
unsortedArray = [1, 3, 4, 8, 2];
// compare the second with the third and leave them
unsortedArray = [1, 3, 4, 8, 2];
// compare the third with the fourth and leave them
unsortedArray = [1, 3, 4, 8, 2];
// compare the fourth with the fifth and swap them
unsortedArray = [1, 3, 4, 2, 8]; // the largest number, 8, ends up at the end

// second iteration excluding the 8 and iterate again

// compare the first with the second and leave them
unsortedArray = [1, 3, 4, 2];
// compare the second with the third and leave them
unsortedArray = [1, 3, 4, 2];
// compare the third with the fourth and swap them
unsortedArray = [1, 3, 2, 4]; // the next largest number, 4, ends up at the end

// third iteration excluding the 4 and iterate again

// compare the first with the second and leave them
unsortedArray = [1, 3, 2];
// compare the second with the third and swap them
unsortedary = [1, 2, 3]; // the next number, 3, ends up at the end

// fourth iteration excluding the 3 and iterate again

// compare the first with the second and leave them
unsortedArray = [1, 2]; // END

If we look closely, we can discern a hidden pattern in the code; after each iteration, the result is N - i, where N is the size of the array and i is the number of iterations we have performed so far.

const unsortedArray = [3, 1, 4, 8, 2];

// first iteration N - i = 4
// result of the first iteration = [1, 3, 4, 2]

// second iteration N - i = 3
// result of the second iteration = [1, 3, 2]

// third iteration N - i = 2
// result of the third iteration = [1, 2]

If we generalize the pattern, we can say that the final result would be N - N + 1 because the generalized way to calculate the sum of elements in an array is: ((N + 1) * N) / 2

Sum between 1 and 10 is 11
Sum between 2 and 9 is 11
Sum between 3 and 8 is 11
Sum between 4 and 7 is 11
.
.
.
Sum between 5 and 6 is 11
So, we can say that with N being 5 and N + 1 being 6, the final result would be
(6 + 1) * 5 / 2 = 11

Now, if we generalize the pattern within Big O notation, we can say that:

1- N (N + 1) / 2
2- N (N + 1) // removing constants elevating everything to 2
3- N^2 + N
// in Big O, we remove less significant values, if we're talking about VERY large numbers,
// + N is VERY small in comparison
4- N^2

Thus, it remains O(N^2) in Big O notation

Code

function bubbleSort(array: number[]): number[] {
  // define the size of the array
  const N = array.length;

  // iterate over the array


  for (let i = 0; i < N; i++) {
    // iterate over the array
    for (let j = 0; j < N - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        // if it is greater, swap the elements
        const temp = array[j];

        // swap the element with the next one
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }

  return array;
}