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

The big O symbol was first introduced by The German number theorist Paul Bachmann in his 1892 book Analytische Zahlentheorie. We often use the big O notation to express the time complexity, and note that it is the time complexity of an algorithm. Big O just means that there is an upper bound, and by definition if f(n)=O (n), then obviously f(n)=O

Why is the big O notation useful? So what is the big O notation? The big O notation is used to analyze the efficiency of an algorithm, indicating the rate at which the input size of the algorithm grows as the input approaches infinity.

For example, suppose we have a barber who takes an average of 30 minutes to give a haircut to a customer. As the line of his customers grows, the time he needs to work will be linearly proportional to the number of customers waiting in line.

That’s because he usually takes about 30 minutes to cut each customer’s hair. This gives us an idea of how long it takes to reach 10, 20 or even 100,000 customers.

Because haircuts are fixed, it is always possible to calculate how long it takes him to serve any number of customers by multiplying the number of customers by 30 minutes. With that in mind, we can classify his efficiency as linear.

In terms of big O, it is O(n)O(n)O(n), where N is equal to the number of customers, and the time required for the barber to complete the work is in a linear or proportional relationship with the number of customers. We use the same technology to determine the efficiency of the algorithm, and we can understand the change of its time efficiency by classifying a given function.

function linearFunc(arr){
    for (let i = 0; i < arr.length; i++) {
        console.log(1000 * 10000); }}const arr = [1.2.3.4.5.6.7];

linearFunc(arr);
Copy the code

Let’s create an easy-to-understand function that is as efficient as a hairdresser. So this function is the same linear as our barber. The input of the function is an array, and the calculation time of 1000*100,000 in each iteration loop body is fixed. The number of times of this event root loop is independent, and the expression usage time and haircut time are fixed.

For the above function, if you increase the length of the array to 1000,000 and console.log(1+1), the efficiency of this function is still the same, because it is linear with the input. Ignore all these constants and say that this function is linearly extended, or big O of n.

function linearFunc(arr){
    for (let i = 0; i < arr.length; i++) {
        console.log(1000 * 10000);
        let something = 1000 * 1000
        console.log(something)
    }
}

const arr = [1.2.3.4.5.6.7];

linearFunc(arr);
Copy the code

constant

A constant is any operation that does not vary with the input to the function. In the following function, the computation time and the return value of the function are fixed, they don’t change with the input, so this is the constant, and for the constant complexity is O(1)O(1)O(1).

function constants(arr){
    let result = 100*1000;
    return result
}
Copy the code
function linearFunc(arr){
    for (let i = 0; i < arr.length; i++) {
        console.log(1000 * 10000);
        let something = 1000 * 1000
        console.log(something)
    }
}
Copy the code

In this function, for is O(n)O(n)O(n), and the time complexity of the internal statements is O(1)O(1)O(1).

O (n) + O (1) + O (1) + O (1) O (n) + O (1) + O (1) + O (1) O (n) + O (1) + O (1) + O (1) here we only care about high time complexity and ignore time complexity is lower, O(1)O(1)O(1), so the top function is O(n)O(n)O(n).