Big O notation is a mathematical concept used in computer science to describe the efficiency of algorithms. It is a useful tool for measuring the runtime and space complexity of an algorithm. However, it is not the only way to analyze algorithms. In this blog post, we will explore Big O notation, other alternatives, and how to apply them in real life.

Big O Notation

Big O notation is a way to describe the upper bound of an algorithm’s runtime or space complexity. It is denoted as O(f(n)), where f(n) is a function that represents the time or space complexity of the algorithm. The most common time complexities are O(1), O(log n), O(n), O(n log n), O(n²), and O(2^n). A constant-time algorithm has a time complexity of O(1), while an algorithm that has to iterate through every element in an array has a time complexity of O(n).

Big O notation is a useful tool for comparing the efficiency of different algorithms. If two algorithms have the same time complexity, they will take roughly the same amount of time to run on the same input. However, it is important to note that Big O notation only describes the upper bound of an algorithm’s runtime. It does not provide information about the best-case or average-case scenario.

Big O notation is a useful tool for analyzing the efficiency of algorithms, but it is not the only way. Omega notation and Theta notation can also be useful in certain situations. By applying these concepts in real life, developers can optimize their code and improve the performance of their websites and apps.

So you worked extremely hard to save more CPU cycle in the central loop but your code still slowly ? I think that you need to know more about time complexity .

“Hey, but what’s time complexity ?”

Time complexity is related how your code spend time, memory and cpu according of size of input. For example, if we will want to answer some questions such as “ If my algorithm spends 1 minute to process a 1000-byte input, how many minutes does it spend to process 2000-byte input ?”

A direct way of calculating complexity would be to find some formula that gives the exact number of operations done by the algorithm to arrive at the result, depending on the size of the input.

 for(i=0; i<N; i++){
     print(i);
 }

So we could say that time spent is

T(N) =
    N*(time spent by a comparison betwhen i and N) +
    N*(time spent to increase i) +
    N*(time spent by a print)

However, it takes a lot work to make a super accurate account of these and usually neither is it worth it. For example, suppose we’ve worked hard and discovered that a certain algorithm spends time.

 T(N) = 10*N² + 137*N + 15

In this case the quadratic term 10 * N² is more important than the others because for almost any value of N it will dominate the sum total. From N ≥ 14 the quadratic term is already responsible for most of the execution time and for N > 1000 it is already responsible for more than 99%. For estimation purposes we could simplify the formula for T (N) = 10 * N² without losing much.

Another point at which we can simplify our formula is the constant factor multiplying the N². To predict how fast the runtime grows depending on the input, it does not matter whether T (N) = 10 * N or T (N) = 1000 * N; in both cases doubling the N will quadruple the execution time.

Therefore, the most popular way of working with time and space complexity in algorithm analysis is asymptotic complexity, which ignores these constant factors and the slower growing terms. It is now that the story of O-big, Θ-big and Ω-big comes in: these are notations that we use to characterize an asymptotic complexity.

Let’s start with O-large, which is a way to give an upper bound on the time spent by an algorithm. (G) describes the class of functions that grow at most as fast as the function g and when we say that f ∈ O (g) we mean that g grows at least as fast as f. Formally:

Given the two functions f and g, we say that f ∈ O (g) if there exist constants x0 and c such that for all x> x0 is f (x) <c * g (x)

In this definition, the constant c gives us scope to ignore constant factors (which allows us to say that 10 * N is O (N)) and the constant x0 says that we only care for the behavior of f and g when N is large and terms that grow faster dominate the total value.

For a concrete example, consider that time function f (n) = 10 * N ^ 2 + 137 * N + 15 from before. We can say that its growth is quadratic:

We can say that f ∈ O (N²), since for c = 11 and N>

10 * N 2 + 137 * N + 15

We can choose other values ​​for c and x0, for example c = 1000 and N> 1000 (which make the account quite obvious). The exact value of these pairs does not matter, what matters is being able to convince yourself that at least one of them exists.

In the opposite direction of the big O we have the big Ω, which is for lower bounds. When we say that f is Ω (g), we are saying that f grows at least as fast as g. In our recurrent example, we can also say that f (n) grows as fast as a quadratic function:

We can say that f is Ω (N²), since for c = 1 and N> 0 it is valid

10 * N² + 137 * N + 15> c * N ^ 2

Finally, Θ-large has to do with fair approximations, when f and g grow at the same rate (except for a possible constant factor). The difference between Θ-large for O-large and Ω-large is that they assume loose approximations, (eg N² ∈ O (N³)) in which one of the functions grows much faster than the other.

Of these three notations, the most common to see is that of the O-grande. Normally, complexity analyzes are only concerned with the worst case execution time so the upper limit given by O-large is sufficient.

Other Alternatives

While Big O notation is the most common way to analyze algorithms, there are other alternatives that can be useful in certain situations. One such alternative is Omega notation, which describes the lower bound of an algorithm’s runtime. Omega notation is denoted as Ω(f(n)). If an algorithm has a time complexity of Ω(f(n)), it means that its runtime cannot be faster than f(n) for any input size.

Another alternative is Theta notation, which describes both the upper and lower bounds of an algorithm’s runtime. Theta notation is denoted as Θ(f(n)). If an algorithm has a time complexity of Θ(f(n)), it means that its runtime is between O(f(n)) and Ω(f(n)) for all input sizes.

Applying Big O Notation in Real Life

Big O notation can be applied in real-life scenarios, such as optimizing code for a website or app. By analyzing the time and space complexity of different algorithms, developers can choose the most efficient one for their needs. For example, if a website needs to sort a large amount of data, an algorithm with a time complexity of O(n log n) would be more efficient than one with a time complexity of O(n²).

Another real-life application of Big O notation is in database optimization. By analyzing the time complexity of database queries, developers can optimize them to run faster and more efficiently. This can lead to faster load times for websites and apps, improving the user experience.

Conclusion

Big O notation is a useful tool for analyzing the efficiency of algorithms, but it is not the only way. Omega notation and Theta notation can also be useful in certain situations. By applying these concepts in real life, developers can optimize their code and improve the performance of their websites and apps.

Check out the Big O notation for more info on how to get the most out of