Where to find what O (n ^ 2) and O (n), etc. mean?

Question

I have noticed stack overflow answers that use such terms, but I don't know what they mean. What did they call and is there a good resource that can explain them in simple words?

Answer 1

This notation is called the Big O notation and is used as a shorthand expression for expressing algorithmic complexity (basically, how long this algorithm will take to run when the input size (n) increases)

Generally speaking, you will come across the following basic types of algorithms:

• O (1) - Constant. The duration of this algorithm does not depend on the number of elements that the algorithm should process.
• O (log n) - Logarithmic - The duration this algorithm takes to complete depends on the number of elements that the algorithm should process. As the input size becomes larger, less time is required for each new input.
• O (n) - linear - the time this algorithm takes to complete depends on the number of elements that the algorithm should process. As the input size increases, the time spent on it grows in equal amounts.
• O (n ^ 2) - Polynominal. As the input size increases, the time spent on processing the input increases by a larger and larger number - this means that the large input sizes become unacceptably difficult to solve.
• O (2 ^ n) - Exponential - the most complex types of problems. Processing time increases depending on the size of the input to an extreme degree.

Typically, you can get a rough estimate of the complexity of an algorithm by looking at how it is used. For example, considering the following method:

function sum(int[] x) { int sum = 0; for (int i = 0; i < x.length; i++) { sum += x[i]; } return sum; } 

Here are a few things to do here:

• Initialize a variable named sum
• Initialize variable i
• For each iteration i: add x [i] to sum, add 1 to i, check if I am less than x.length
• Refundable amount

There are several operations that are performed for a constant time (the first two and the last), since the size x does not affect the duration. In addition, there are some operations performed in linear time (since they are performed once for each entry in x). With the Big O note, the algorithm is simplified to the most complex, so the algorithm of this sum will work in O (n)

Answer 2

Read Computational Complexity first , then try some books on algorithms such as Introduction to Algorithms .

Material from Wikipedia:

Big O signs characterize growth functions

If you do not understand the details, you can very often approximate the complexity of an algorithm by analyzing its code:

 void simpleFunction(arg); // O(1) - if number of function instructions is constant and don't depend on number of input size for (int i=0;i<n;i++) {simpleFunction(element[i]);} // O(n) for (int i=0;i<n;i++) { // this one runs O(n^2) for (int j=0;j<n;j++) { simpleFunction(element[i]); } } for (int i=0;i<n;i*=2) { // O(lgn) simpleFunction(element[i]); } 

Sometimes it is not so easy to evaluate the complexity of a large O function / algorithm notation in such cases, amortized analysis . The above code should only be used as a quick start.

Answer 3

This is called Big O notation and is used to quantify the complexity of algorithms.

O (1) means that the algorithm takes a constant time no matter how much data needs to be processed.

O (n) means that the speed of the algorithm grows linearly with the amount of data.

etc.

So, the lower the power n in the O notation, the better your algorithm to solve the problem. The best case is O (1) (n = 0). But in many problems there is complex complexity, so you will not find such an ideal algorithm in almost all cases.

Answer 4

The answers are good. The main term for web search is "Big O notation".

The basic idea of ​​the math “someformula is O (someterm)” is that since your variable goes to infinity, “someterm” is part of the formula that dominates.

For example, suppose you have 0.05*x^3 + 300*x^2 + 200000000*x + 10 . For very small sizes x (x == 1 or x == 2), that 200000000*x will by far be the biggest part. At this point, the formula graph will look linear. As you move, at some point, the 300*x^2 will be larger. However, if you keep making x even bigger, as large as possible, the 0.05*x^3 will be the largest and ultimately get ahead of the rest of the formula. This is where it becomes clear on the graph that you are looking at a cubic function. So we would say that the formula is O(x^3) .