DEV Community π©βπ»π¨βπ» is a community of 966,904 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Mauricio Reatto Duarte

Posted on • Originally published at atalkwith.dev on

Do you know what is Big O Notation?

As we need to improve our abilities as software engineer, we need to stop abusing the power of the language weβre using and start acting as an analyst for the effectiveness of an algorithm application. This post will explain the concept of Big O Notation , and how to analyze an implementation of an algorithm on time (execution time) and space (memory consumed).

The number of inputs

Analyzing with the Big O Notation rides you to following question: βWhat happens with n approaches to the infinity?β. In other words, it will tell you about the algorithm.

https://images.app.goo.gl/UDf6DhkMH3hM5Xsw6

Time complexities examples

Big-O Notation rules

Letβs say that an algorithmβs complexity as f(n):

• n - The number of inputs
• f(n)space - The additional memory
• f(n)time - The time needed

The goal of the analysis is calculate the efficiency of the algorithm by calculating f(n), but because of it difficulty, we can use the Big-O Notation rules for that.

The first, second, fourth and sixty need to be in your mind, because they are commonly used.

• Sum: If f(n) is O(h(n)) and g(n) is O(p(n)), then f(n)+g(n) is O(h(n)+p(n)). Itβs the sum of two Big-O notations.
• Product: If f(n) is O(h(n)) and g(n) is O(p(n)), then f(n)g(n) is O(h(n)p(n)). Itβs the multiplication of Big-O notations.
• Log: log(nk) is O(log(n)) for any constant k > 0. With the log, constants within a log function are also ignored in Big-O notation.
• Polynomial: If f(n) is a polynomial of degree k, then f(n) is O(nk). The polynomial time complexities have Big-O notation of the same polynomial degree.
• Transitive: If f(n) is O(g(n)) and g(n) is O(h(n)), then f(n) is O(h(n)). The time complexity has the same Big-O notation.
• Coefficient: If f(n) is O(g(n)), then kf(n) is O(g(n)), for any constant k > 0.

Examples

sum - O(n) = n

``````function s(n) {
var total = 0;
for (var i = 0; i < n; i++) {
total += 1;
}
for (var i = 0; i < 8 * n; i++) {
total += 1;
}

}
``````

product - O(n)=n^2

``````function prod(n) {
var total = 0;
for (var i = 0; i < n; i++){
total += 1;
for (var i = 0; i < 6 * n; i++){
total += 1;
}
}

}
``````

polynomial - O(nΛk)

``````function poly(n) {
var total = 0;
for (var i = 0; i < n * n; i++) {
total += 1;
}

}
``````

coefficient - O(n)

``````function coef(n) {
var total = 0;
for (var i = 0; i < n; i++) {
total += 1;
}