678-826-2866
What is Big O and why is it important?
Big O notation is a critical mathematical concept used in computer science to describe the performance or complexity of an algorithm, specifically in terms of time complexity and memory usage. It is essential in software development for understanding how an algorithm will scale with increasing size of inputs. The notation provides a simplified understanding of the algorithm in terms of its efficiency and scalability.
Algorithm performance can be described as a mathematical equation. Each step of the algorithm adds to the complexity of the equation. To demonstrate how an algorithm can be analyzed and converted into Big O notation, let's consider a simple example: a function that finds the maximum value in an unsorted list of numbers.
1. function findMax(numbers){
2. if(numbers is empty){
3. return null;
4. }
5.
6. maxNumber = numbers[0];
7.
8. for(each number in numbers){
9. if(number > maxNumber){
10. maxNumber = number;
11. }
12. }
13.
14. return maxNumber;
15. } Line 2 will do a check if the list is empty. No matter the list size, this check will take the same amount of time, so this is a constant time operation: 1. Line 6 will assign the first value in the list to the maxNumber variable, so it will always take the same amount of time despite the list size making it another constant time. Our algorithm performance then becomes: 1+1. On line 8 we will iterate through the entire list provided and do a check on each value, so the larger the list becomes the more time it'll take. Because we only iterate each item once within the loop, this is considered linear time. Our algorithm performance is now: 1+1+n (where n is the list size). Now within the loop we will assign the new value to maxValue in cases where the new value is larger. This wont happen every time but we can estimate, on average, it will occur 50% of the time. Since the highest number can be in any position in the list, it will average out to the middle of the list. That makes our algorithm performance: 1+1+n+0.5n. Simplified, we get:
1.5n+2
In computer science, this level of accuracy is unneeded to determine overall performance at scale. What really matters to us is the max scale of n. The highest scale value tells us at what scale the algorithm will consume time and memory as more data is passed through it. Simplifying to this format results in Big O.
Big O Notations:
- O(1) - Constant Time: The execution time of the algorithm is constant, regardless of the input size.
- O(log n) - Logarithmic Time: The execution time grows logarithmically with the input size. Common in algorithms that divide the problem in half each time (like binary search).
- O(n) - Linear Time: The execution time grows linearly with the input size.
- O(n log n) ? Linear Logarithmic Time: Combines linear and logarithmic growth, common in efficient sorting algorithms like quicksort and mergesort.
- O(n^2) - Quadratic Time: The execution time grows quadratically with the input size. Often seen in algorithms with nested loops over the data.
- O(2^n) - Exponential Time: The execution time doubles with each additional element in the input.
- O(n!) - Factorial Time: The execution time grows factorially, often associated with algorithms that generate all permutations of the input.
In our example, we have n to the 1st power so we are using linear time O(n). That means for each additional item added to the list we will consume a linear amount of time. We can test that by performance testing our code with different list sizes. If our program averages performance at 1000 items per second, we can extrapolate the time needed for any size list.
Application in Perfoamnce Engineering and Site Reliability Engineering (SRE):
In performance engineering, Big O notation is crucial for several reasons. Understanding the time and memory complexity of an algorithm helps in identifying bottlenecks and areas for optimization. Site reliability engineers often work to ensure that systems are scalable and performant, and knowledge of Big O notation is crucial in the development and discovevry process. Big O can be used in capacity planning to predict how systems will behave as load increases. For instance, an algorithm with O(n^2) complexity may not be suitable for a large-scale, high-traffic application due to its potential to degrade performance as data grows. In post-mortems of incidents, analyzing the complexity of algorithms can help in understanding why a system failed under load or why certain operations took longer than expected.
Big O notation provides a framework for understanding and discussing the efficiency and scalability of algorithms and systems. This understanding is critical in SRE, as it directly impacts the reliability, performance, and scalability of the services and infrastructure managed.
