DSA (Data Structure and Algorithms) is a well known subject in past and modern programming environment, and despite all the fuzz about AI and how LLM’s models can/are/will change the way that we as software engineers solve problems, I still believe that understanding DSA concepts are gonna play a huge role on leveraging what LLM’s models can/how they write the code that we tell them to write. So without further do, let’s dive deep on the most important Data Structures and Algorithms.

🏢 Big O Notation

Big O Notation is a mathematical way to evaluate the efficiency of an algorithm. It describes how the runtime or memory usage of an algorithm grows as the size of the input increases. In other words, it helps us understand the scalability of algorithms and data structures by focusing on their performance trends rather than exact execution times.

<aside> 💡

"Big-O Complexity Chart" from Big-O Cheat Sheet, created by Eric Drowell.

</aside>

As we can see there is different types of complexities.

Being the most performant the green ones and the less performant the red ones in the chart.

Let’s understand what they mean:

• O(1) [Constant]: When the complexity of time and space remains the same no matter the size of the input in an algorithm.
• O(log n) [Logarithmic]: When an algorithm decreases the complexity of time and space in memory during his execution (e.g. Binary search in sorted lists)

*Binary search can be only applied in sorted lists - we will see that later.

• O(n) [Linear]: When an algorithm has an increased complexity of time and space in memory due an input size.
• O(n log n) [Log linear]: This complexity occurs when an algorithm must examine all (n) elements but also perform a logarithmic reduction or division of the problem at each step. It’s faster than quadratic time (O(n²)) but slower than linear time (O(n)). Typical examples include efficient sorting algorithms and divide-and-conquer strategies.
• O(n²) [Quadratic]: When the complexity of time and space increases exponentially due an input size (e.g. nested for loops). Means that the time it takes for an algorithm to finish is proportional to the square of the size of the input.
• O(2ⁿ) [Exponential]: When the number of operations of an algorithm doubles with each additional input element. Algorithms with this complexity grow so fast that even small inputs become impractical. For example, if an algorithm takes 2ⁿsteps, then with n=10 it requires 1,024 steps, but with n=20 it already requires over a million steps. often appears in problems that involve exhaustive search, such as generating all subsets of a set, solving the traveling salesman problem with brute force, or certain recursive algorithms without optimization. Because the growth is explosive, exponential algorithms are considered inefficient and are avoided in practice unless the input size is very small or no better solution exists.

Big O Notation consider the worst possible case, therefore if your code look like this:

function findSomething (target: number, data: Array<number>): number | null {	
	if (target === data[0]) return data[0];
	
	for(let i = 0; i < data.length; i++) {
		if (data[i] === target) {
			return data[i];
		}
	}
	
	return null;
}

<aside> 💡

Even if the target we are looking for is at the first index of the array, Big O Notation evaluates the worst-case scenario, where the algorithm might need to iterate through the entire data array. In this case, the complexity is O(n), because the algorithm uses a loop - a for loop - that potentially examines every element.

</aside>

🔍 Binary Search

Binary Search is a algorithm that uses the concept of DC (Divide and Conquer), basically this concept tells that you need to keep dividing your problem into smaller pieces until you find what your looking for or not.