Time complexity – O(n^2), O(n^3), and O(log n)(2)

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

O(n2), O(n3) and O(log⁡n)O(n^2), O(n^3) and O(\log n)O(n2), O(n3) and O(logn) are graphically helpful for understanding the nature of the complexity of these computational functions.

$O(n^2)$

function square(arr){
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            console.log(i,j)            
        }
        
    }
}
Copy the code

In the square function above, there are two nested for loops, inside which console.log(I,j) is performed. This is a constant time complexity, which can be viewed as traversing a matrix, For example, square(4) calculates console.log(I,j) times 4×44 times 4×4 for I and j, 42=164^2 = 1642=16, so the time complexity is N2n ^2n2

$O(n^3)$

function cube(arr){
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            for (let k = 0; k < arr.length; k++) {
                console.log(i,j,k)  
            }
        }
    }
}
Copy the code

A 3-layer nested for loop can be mapped to a cube, assuming I is the column index, j is the row index, and K is the high index, growing along the Z (k) axis first, Then the j-axis finally stacks the two-dimensional plane of j and K along the i-axis to form the cube so 4×4×4=644 \times 4 \times 4=644 ×4×4=64 or O(n3)O(n^3)O(n3)

$O(\log(n))$

So far it’s been n to some power to get the time complexity, so here’s the picture, something to the power of something is 8, and I’m sure you’ll be able to figure out 2 to the third pretty soon. So if you want to do it in general, it’s log base two.

function logFunc(n){
    if(n===0) return "Done"
    n = Math.floor(n / 2);
    return logFunc(n)
}

Copy the code

The function up here is a function that calls itself recursively, at the level it divides n by 2 and exits with n===0 and we’re graphically calling it, moving itself 3 times, so this is 3 levels of recursion. N =8 is 3 and if you write the relationship as a function, you can write log⁡n\log nlogn which is log base 2 of n is the complexity of the function.