Quick note, my answer is almost certainly confusing Big Oh notation (which is an upper bound) with Big Theta notation "Θ" (which is a two-side bound). But in my experience, this is actually typical of discussions in non-academic settings. Apologies for any confusion caused.

BigOh complexity can be visualized with this graph:

The simplest definition I can give for Big Oh notation is this:

Big Oh notation is a relative representation of the complexity of an algorithm.

There are some important and deliberately chosen words in that sentence:

• relative: you can only compare apples to apples. You can't compare an algorithm that does arithmetic multiplication to an algorithm that sorts a list of integers. But a comparison of two algorithms to do arithmetic operations (one multiplication, one addition) will tell you something meaningful;
• representation: BigOh (in its simplest form) reduces the comparison between algorithms to a single variable. That variable is chosen based on observations or assumptions. For example, sorting algorithms are typically compared based on comparison operations (comparing two nodes to determine their relative ordering). This assumes that comparison is expensive. But what if the comparison is cheap but swapping is expensive? It changes the comparison; and
• complexity: if it takes me one second to sort 10,000 elements, how long will it take me to sort one million? Complexity in this instance is a relative measure to something else.

Come back and reread the above when you've read the rest.

The best example of BigOh I can think of is doing arithmetic. Take two numbers (123456 and 789012). The basic arithmetic operations we learned in school were:

• addition;
• subtraction;
• multiplication; and
• division.

Each of these is an operation or a problem. A method of solving these is called an algorithm.

The addition is the simplest. You line the numbers up (to the right) and add the digits in a column writing the last number of that addition in the result. The 'tens' part of that number is carried over to the next column.

Let's assume that the addition of these numbers is the most expensive operation in this algorithm. It stands to reason that to add these two numbers together we have to add together 6 digits (and possibly carry a 7th). If we add two 100 digit numbers together we have to do 100 additions. If we add two 10,000 digit numbers we have to do 10,000 additions.

See the pattern? The complexity (being the number of operations) is directly proportional to the number of digits n in the larger number. We call this O(n) or linear complexity.

Subtraction is similar (except you may need to borrow instead of carry).

Multiplication is different. You line the numbers up, take the first digit in the bottom number and multiply it in turn against each digit in the top number and so on through each digit. So to multiply our two 6 digit numbers we must do 36 multiplications. We may need to do as many as 10 or 11 column adds to get the end result too.

If we have two 100-digit numbers we need to do 10,000 multiplications and 200 adds. For two one million digit numbers we need to do one trillion (10¹²) multiplications and two million adds.

As the algorithm scales with n-squared, this is O(n²) or quadratic complexity. This is a good time to introduce another important concept:

We only care about the most significant portion of complexity.

The astute may have realized that we could express the number of operations as: n² + 2n. But as you saw from our example with two numbers of a million digits apiece, the second term (2n) becomes insignificant (accounting for 0.0002% of the total operations by that stage).

One can notice that we've assumed the worst case scenario here. While multiplying 6 digit numbers, if one of them has 4 digits and the other one has 6 digits, then we only have 24 multiplications. Still, we calculate the worst case scenario for that 'n', i.e when both are 6 digit numbers. Hence Big Oh notation is about the Worst-case scenario of an algorithm.

The Telephone Book

The next best example I can think of is the telephone book, normally called the White Pages or similar but it varies from country to country. But I'm talking about the one that lists people by surname and then initials or first name, possibly address and then telephone numbers.

Now if you were instructing a computer to look up the phone number for "John Smith" in a telephone book that contains 1,000,000 names, what would you do? Ignoring the fact that you could guess how far in the S's started (let's assume you can't), what would you do?

A typical implementation might be to open up to the middle, take the 500,000^th and compare it to "Smith". If it happens to be "Smith, John", we just got really lucky. Far more likely is that "John Smith" will be before or after that name. If it's after we then divide the last half of the phone book in half and repeat. If it's before then we divide the first half of the phone book in half and repeat. And so on.

This is called a binary search and is used every day in programming whether you realize it or not.

So if you want to find a name in a phone book of a million names you can actually find any name by doing this at most 20 times. In comparing search algorithms we decide that this comparison is our 'n'.

• For a phone book of 3 names it takes 2 comparisons (at most).
• For 7 it takes at most 3.
• For 15 it takes 4.
• …
• For 1,000,000 it takes 20.

That is staggeringly good, isn't it?

In BigOh terms this is O(log n) or logarithmic complexity. Now the logarithm in question could be ln (base e), log₁₀, log₂ or some other base. It doesn't matter it's still O(log n) just like O(2n²) and O(100n²) are still both O(n²).

It's worthwhile at this point to explain that BigOh can be used to determine three cases with an algorithm:

• Best Case: In the telephone book search, the best case is that we find the name in one comparison. This is O(1) or constant complexity;
• Expected Case: As discussed above this is O(log n); and
• Worst Case: This is also O(log n).

Normally we don't care about the best case. We're interested in the expected and worst case. Sometimes one or the other of these will be more important.

Back to the telephone book.

What if you have a phone number and want to find a name? The police have a reverse phone book but such look-ups are denied to the general public. Or are they? Technically you can reverse look-up a number in an ordinary phone book. How?

You start at the first name and compare the number. If it's a match, great, if not, you move on to the next. You have to do it this way because the phone book is unordered (by phone number anyway).

So to find a name given the phone number (reverse lookup):

• Best Case: O(1);
• Expected Case: O(n) (for 500,000); and
• Worst Case: O(n) (for 1,000,000).

The Traveling Salesman

This is quite a famous problem in computer science and deserves a mention. In this problem, you have N towns. Each of those towns is linked to 1 or more other towns by a road of a certain distance. The Traveling Salesman problem is to find the shortest tour that visits every town.

Sounds simple? Think again.

If you have 3 towns A, B, and C with roads between all pairs then you could go:

• A → B → C
• A → C → B
• B → C → A
• B → A → C
• C → A → B
• C → B → A

Well, actually there's less than that because some of these are equivalent (A → B → C and C → B → A are equivalent, for example, because they use the same roads, just in reverse).

In actuality, there are 3 possibilities.

• Take this to 4 towns and you have (iirc) 12 possibilities.
• With 5 it's 60.
• 6 becomes 360.

This is a function of a mathematical operation called a factorial. Basically:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
• …
• 25! = 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000
• …
• 50! = 50 × 49 × … × 2 × 1 = 3.04140932 × 10⁶⁴

So the BigOh of the Traveling Salesman problem is O(n!) or factorial or combinatorial complexity.

By the time you get to 200 towns there isn't enough time left in the universe to solve the problem with traditional computers.

Something to think about.

Polynomial Time

Another point I wanted to make a quick mention of is that any algorithm that has a complexity of O(n^a) is said to have polynomial complexity or is solvable in polynomial time.

O(n), O(n²) etc. are all polynomial time. Some problems cannot be solved in polynomial time. Certain things are used in the world because of this. Public Key Cryptography is a prime example. It is computationally hard to find two prime factors of a very large number. If it wasn't, we couldn't use the public key systems we use.

Anyway, that's it for my (hopefully plain English) explanation of BigOh (revised).

It shows how an algorithm scales based on input size.

O(n²): known as Quadratic complexity

• 1 item: 1 operations
• 10 items: 100 operations
• 100 items: 10,000 operations

Notice that the number of items increases by a factor of 10, but the time increases by a factor of 10². Basically, n=10 and so O(n²) gives us the scaling factor n² which is 10².

O(n): known as Linear complexity

• 1 item: 1 operation
• 10 items: 10 operations
• 100 items: 100 operations

This time the number of items increases by a factor of 10, and so does the time. n=10 and so O(n)'s scaling factor is 10.

O(1): known as Constant complexity

• 1 item: 1 operations
• 10 items: 1 operations
• 100 items: 1 operations

The number of items is still increasing by a factor of 10, but the scaling factor of O(1) is always 1.

O(log n): known as Logarithmic complexity

• 1 item: 1 operations
• 10 items: 2 operations
• 100 items: 3 operations
• 1000 items: 4 operations
• 10,000 items: 5 operations

The number of computations is only increased by a log of the input value. So in this case, assuming each computation takes 1 second, the log of the input n is the time required, hence log n.

That's the gist of it. They reduce the maths down so it might not be exactly n² or whatever they say it is, but that'll be the dominating factor in the scaling.

EDIT: Quick note, this is almost certainly confusing Big O notation (which is an upper bound) with Theta notation (which is both an upper and lower bound). In my experience this is actually typical of discussions in non-academic settings. Apologies for any confusion caused.

In one sentence: As the size of your job goes up, how much longer does it take to complete it?

Obviously that's only using "size" as the input and "time taken" as the output — the same idea applies if you want to talk about memory usage etc.

Here's an example where we have N T-shirts which we want to dry. We'll assume it's incredibly quick to get them in the drying position (i.e. the human interaction is negligible). That's not the case in real life, of course...

• Using a washing line outside: assuming you have an infinitely large back yard, washing dries in O(1) time. However much you have of it, it'll get the same sun and fresh air, so the size doesn't affect the drying time.

• Using a tumble dryer: you put 10 shirts in each load, and then they're done an hour later. (Ignore the actual numbers here — they're irrelevant.) So drying 50 shirts takes about 5 times as long as drying 10 shirts.

• Putting everything in an airing cupboard: If we put everything in one big pile and just let general warmth do it, it will take a long time for the middle shirts to get dry. I wouldn't like to guess at the detail, but I suspect this is at least O(N^2) — as you increase the wash load, the drying time increases faster.

One important aspect of "big O" notation is that it doesn't say which algorithm will be faster for a given size. Take a hashtable (string key, integer value) vs an array of pairs (string, integer). Is it faster to find a key in the hashtable or an element in the array, based on a string? (i.e. for the array, "find the first element where the string part matches the given key.") Hashtables are generally amortised (~= "on average") O(1) — once they're set up, it should take about the same time to find an entry in a 100 entry table as in a 1,000,000 entry table. Finding an element in an array (based on content rather than index) is linear, i.e. O(N) — on average, you're going to have to look at half the entries.

Does this make a hashtable faster than an array for lookups? Not necessarily. If you've got a very small collection of entries, an array may well be faster — you may be able to check all the strings in the time that it takes to just calculate the hashcode of the one you're looking at. As the data set grows larger, however, the hashtable will eventually beat the array.

Big O describes an upper limit on the growth behaviour of a function, for example the runtime of a program, when inputs become large.

Examples:

• O(n): If I double the input size the runtime doubles

• O(n²): If the input size doubles the runtime quadruples

• O(log n): If the input size doubles the runtime increases by one

• O(2ⁿ): If the input size increases by one, the runtime doubles

The input size is usually the space in bits needed to represent the input.

Big O is just a way to "Express" yourself in a common way, "How much time / space does it take to run my code?".

You may often see O(n), O(n²), O(nlogn) and so forth, all these are just ways to show; How does an algorithm change?

O(n) means Big O is n, and now you might think, "What is n!?" Well "n" is the amount of elements. Imaging you want to search for an Item in an Array. You would have to look on Each element and as "Are you the correct element/item?" in the worst case, the item is at the last index, which means that it took as much time as there are items in the list, so to be generic, we say "oh hey, n is a fair given amount of values!".

So then you might understand what "n²" means, but to be even more specific, play with the thought you have a simple, the simpliest of the sorting algorithms; bubblesort. This algorithm needs to look through the whole list, for each item.

My list

1. 1
2. 6
3. 3

The flow here would be:

• Compare 1 and 6, which is biggest? Ok 6 is in the right position, moving forward!
• Compare 6 and 3, oh, 3 is less! Let's move that, Ok the list changed, we need to start from the begining now!

This is O n² because, you need to look at all items in the list there are "n" items. For each item, you look at all items once more, for comparing, this is also "n", so for every item, you look "n" times meaning n*n = n²

I hope this is as simple as you want it.

But remember, Big O is just a way to experss yourself in the manner of time and space.

Big O describes the fundamental scaling nature of an algorithm.

There is a lot of information that Big O does not tell you about a given algorithm. It cuts to the bone and gives only information about the scaling nature of an algorithm, specifically how the resource use (think time or memory) of an algorithm scales in response to the "input size".

Consider the difference between a steam engine and a rocket. They are not merely different varieties of the same thing (as, say, a Prius engine vs. a Lamborghini engine) but they are dramatically different kinds of propulsion systems, at their core. A steam engine may be faster than a toy rocket, but no steam piston engine will be able to achieve the speeds of an orbital launch vehicle. This is because these systems have different scaling characteristics with regards to the relation of fuel required ("resource usage") to reach a given speed ("input size").

Why is this so important? Because software deals with problems that may differ in size by factors up to a trillion. Consider that for a moment. The ratio between the speed necessary to travel to the Moon and human walking speed is less than 10,000:1, and that is absolutely tiny compared to the range in input sizes software may face. And because software may face an astronomical range in input sizes there is the potential for the Big O complexity of an algorithm, it's fundamental scaling nature, to trump any implementation details.

Consider the canonical sorting example. Bubble-sort is O(n²) while merge-sort is O(n log n). Let's say you have two sorting applications, application A which uses bubble-sort and application B which uses merge-sort, and let's say that for input sizes of around 30 elements application A is 1,000x faster than application B at sorting. If you never have to sort much more than 30 elements then it's obvious that you should prefer application A, as it is much faster at these input sizes. However, if you find that you may have to sort ten million items then what you'd expect is that application B actually ends up being thousands of times faster than application A in this case, entirely due to the way each algorithm scales.

Big O is a measure of how much time/space an algorithm uses relative to the size of its input.

If an algorithm is O(n) then the time/space will increase at the same rate as its input.

If an algorithm is O(n²) then the time/space increase at the rate of its input squared.

and so on.

A simple straightforward answer can be:

Big O represents the worst possible time/space for that algorithm. The algorithm will never take more space/time above that limit. Big O represents time/space complexity in the extreme case.

Definition :- Big O notation is a notation which says how a algorithm performance will perform if the data input increases.

When we talk about algorithms there are 3 important pillars Input , Output and Processing of algorithm. Big O is symbolic notation which says if the data input is increased in what rate will the performance vary of the algorithm processing.

I would encourage you to see this youtube video which explains Big O Notation in depth with code examples.

So for example assume that a algorithm takes 5 records and the time required for processing the same is 27 seconds. Now if we increase the records to 10 the algorithm takes 105 seconds.

In simple words the time taken is square of the number of records. We can denote this by O(n ^ 2). This symbolic representation is termed as Big O notation.

Now please note the units can be anything in inputs it can be bytes , bits number of records , the performance can be measured in any unit like second , minutes , days and so on. So its not the exact unit but rather the relationship.

For example look at the below function "Function1" which takes a collection and does processing on the first record. Now for this function the performance will be same irrespective you put 1000 , 10000 or 100000 records. So we can denote it by O(1).

void Function1(List<string> data)
{
string str = data[0];
}

Now see the below function "Function2()". In this case the processing time will increase with number of records. We can denote this algorithm performance using O(n).

void Function2(List<string> data)
        {
            foreach(string str in data)
            {
                if (str == "shiv")
                {
                    return;
                }
            }
        }

When we see a Big O notation for any algorithm we can classify them in to three categories of performance :-

1. Log and constant category :- Any developer would love to see their algorithm performance in this category.
2. Linear :- Developer will not want to see algorithms in this category , until its the last option or the only option left.
3. Exponential :- This is where we do not want to see our algorithms and a rework is needed.

So by looking at Big O notation we categorize good and bad zones for algorithms.

I would recommend you to watch this 10 minutes video which discusses Big O with sample code

https://www.youtube.com/watch?v=k6kxtzICG_g

Preface

algorithm: procedure/formula for solving a problem

How do analyze algorithms and how can we compare algorithms against each other?

example: you and a friend are asked to create a function to sum the numbers from 0 to N. You come up with f(x) and your friend comes up with g(x). Both functions have the same result, but a different algorithm. In order to objectively compare the efficiency of the algorithms we use Big-O notation.

Big-O notation: describes how quickly runtime will grow relative to the input as the input get arbitrarily large.

3 key takeaways:

1. Compare how quickly runtime grows NOT compare exact runtimes (depends on hardware)
2. Only concerned with runtime grow relative to the input (n)
3. As n gets arbitrarily large, focus on the terms that will grow the fastest as n gets large (think infinity) AKA asymptotic analysis

Space complexity: aside from time complexity, we also care about space complexity (how much memory/space an algorithm uses). Instead of checking the time of operations, we check the size of the allocation of memory.

Big O is a means to represent the upper bounds of any function. We generally use it for expressing the upper bounds of a function that tells the running time of an Algorithm.

Ex : f(n) = 2(n^2) +3n be a function representing the running time of a hypothetical algorithm, Big-O notation essentially gives the upper limit for this function which is O(n^2)

This notation basically tells us that, for any input 'n' the running time won't be greater than the value expressed by Big-O notation.

Also, agree with all the above detailed answers. Hope this helps !!

It represents the speed of an algorithm in the long run.

To take a literal analogy, you don't care how fast a runner can sprint a 100m dash, or even a 5k run. You care more about marathoners, and preferably ultra marathoners (beyond which the analogy to running breaks down and you have to revert to the metaphorical meaning of "the long run").

You can safely stop reading here.

I'm adding this answer because I'm surprised how mathematical and technical the rest of the answers are. The notion of the "long run" in first sentence is related to the arbitrarily time-consuming computational tasks. Unlike running, which is limited by human capacity, computational tasks can take even more than millions of years for certain algorithms to complete.

What about all those mathematical logarithms and polynomials? It turns out that algorithms are intrinsically related to these mathematical terms. If you are measuring the heights of all the kids on the block, it will take you as much time as there are kids. This is intrinsically related to the notion of n^1 or just n where n is nothing more than the number of kids on the block. In the ultra-marathon case, you are measuring the heights of all the kids in your city, but you then have to ignore travel times and assume they are all available to you in a line (otherwise we jump ahead of the current explanation).

Suppose then you are trying to arrange the list that you made of of kids heights in order of shortest height to longest height. If it is just the kids in your neighborhood you might just eyeball it and come up with the ordered list. This is the "sprint" analogy, and we truly don't care about sprints in computer science because why use a computer when you can eyeball something?

But if you were arranging the list of the heights of all kids in your city, or better yet, your country, then you will find that how you do it is intrinsically tied to the mathematical log and n^2. Going through your list to find the shortest kid, writing his name in a separate notebook, and crossing it out from the original notebook is intrinsically tied to the mathematical n^2. If you think of arranging half your notebook, then the other half, and then combining the results, you will arrive at a method that is intrinsically tied to the logarithm.

Finally, suppose you first had to go to the store to buy a measuring tape. This is an example of an effort that is of consequence in short sprints, such as measuring the kids on the block, but when you are measuring all the kids in the city you can safely ignore this cost. This is the intrinsic connection to the mathematical dropping of say lower order polynomial terms.

I hope I have explained that the big-O notation is merely about the long run, that the mathematics is inherently connected to ways of computation, and that the dropping of mathematical terms and other simplifications are connected to the long run in a rather common sense way.

Once you realize this, you'll find the big-O is really super-easy because all the hard high school math just drops out easily. The only difficult part is analyzing an algorithm to identify the mathematical terms, but with some practice you can start dropping terms during the analysis itself and safely ignore chunks of the algorithm to focus only on the part that is relevant to the big-O. I. e. you should be able to eyeball most situations.

Happy big-O-ing, it was my favorite thing about Computer Science -- finding that something was way easier than I thought, and then being able to show off at Google interviews when the uninitiated would be intimidated, lol.

What is a plain English explanation of “Big O” notation?

I would like to stress that the driving motive for “Big O” notation is one thing, when an input size of algorithm gets too big some parts (i.e constants, coefficients, terms )of the equation describing the measure of the algorithm becomes so insignificant that we ignore them. The parts of equation that survives after ignoring some of its parts is termed as the “Big O” notation of the algorithm.

So if the input size is NOT too big the idea of “Big O” notation( upper bound ) will be unimportant.

int sumArray (int[] nums){
    int sum=0;   // here we've 1 operation
    for(int i=0; i < nums.length;i++){   // we've n times
        sum += nums[i]; // taking initialization and assignments, 3 ops
    }
    return sum;
}

In above algorithm, let's say you find out T(n) as follows (time complexity):

T(n) = 3*n + 2

To find its “Big O” notation, we need to consider very big input size:

n= 1,000,000   -> T(1,000,000) = 3,000,002
n=1,000,000,000  -> T(1,000,000,000) = 3,000,000,002
n=10,000,000,000  -> T(10,000,000,000) = 30,000,000,002

Lets give this similar inputs for another function F(n) = n

n= 1,000,000   -> F(1,000,000) = 1,000,000 
n=1,000,000,000  -> F(1,000,000,000) = 1,000,000,000
n=10,000,000,000  -> F(10,000,000,000) = 10,000,000,000

As you can see as input size get too big the T(n) approximately equal to or getting closer to F(n), so the constant 2 and the coefficient 3 are becoming too insignificant, now the idea of Big O” notation comes in,

O(T(n)) = F(n)
O(T(n)) = n

We say the big O of T(n) is n, and the notation is O(T(n)) = n, it is the upper bound of T(n) as n gets too big. the same step applies for other algorithms.

There are some great answers already posted, but I would like to contribute in a different way. If you want to visualize what all is happening you can assume that a compiler can perform close to 10^8 operations in ~1sec. If the input is given in 10^8, you might want to design an algorithm that operates in a linear fashion(like an un-nested for-loop). below is the table that can help you to quickly figure out the type of algorithm you want to figure out ;)

When we have a function like f(n) = n+3 and we want to know how the graph looks likes when n approaches infinity, we just drop all the constants and lower order terms because they don't matter when n gets big. Which leaves us with f(n) = n, so why can't we just use this, why do we need to look for some function which is above and below our f(n) = n+3 function, so big O and big Omega.

Because it would be incorrect to say that the function is just f(n) = n when n approaches infinity, so to be correct we describe the area where the f(n) = n+3 could be. We are not interested where the graph is exactly, because lower order terms and constant don't change the growth of the graph significantly, so in other words the area which is enclosed from upper and lower bound is a vague version of our f(n) = n+3 function.

The mere dropping of the constant and lower order term is exactly the process of finding the function which is below and above.

By definition is a function a lower or upper bound of another function if you can find a constant with whom you can multiply the f(n) = n function so that for every n the output is bigger (or smaller for lower bound) than for the original function:

f(n) = n*C > f(n) = n+3

And yes C = 2 would do it, therefore our function f(n) = n can be an upper bound of our f(x) = x+3 function.

Same for lower bound:

f(n) = n*C < f(n) = n+3

C = -2 would do it

So f(x) = n is the upper and lower bound of f(x) = x+3, when its both big O and Omega than its Theta, which means its tightly bound.

So big O could also be f(x) = x^2 because it fulfills the condition f(n) = n^2*C > f(n) = n+3. Its above our f(n) = n+3 graph, but the area between this upper bound and the lower bound is not as precise as our earlier bounds.

From (source) one can read:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. (..) In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Big O notation does not represent a function per si but rather a set of functions with a certain asymptotic upper-bound; as one can read from source:

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

Informally, in computer-science time-complexity and space-complexity theories, one can think of the Big O notation as a categorization of algorithms with a certain worst-case scenario concerning time and space, respectively. For instance, O(n):

An algorithm is said to take linear time/space, or O(n) time/space, if its time/space complexity is O(n). Informally, this means that the running time/space increases at most linearly with the size of the input (source).

and O(n log n) as:

An algorithm is said to run in quasilinear time/space if T(n) = O(n log^k n) for some positive constant k; linearithmic time/space is the case k = 1 (source).

Nonetheless, typically such relaxed phrasing is normally used to quantify (for the worst-case scenario) how a set of algorithms behaves compared with another set of algorithms regarding the increase of their input sizes. To compare two classes of algorithms (e.g., O(n log n) and O(n)) one should analyze how both classes of algorithms behaves with the increase of their input size (i.e., n) for the worse-case scenario; analyzing n when it tends to the infinity

In the image above big-O denote one of the asymptotically least upper-bounds of the plotted functions, and does not refer to the sets O(f(n)).

For instance comparing O(n log n) vs. O(n) as one can see in the image after a certain input, O(n log n) (green line) grows faster than O(n) (yellow line). That is why (for the worst-case) O(n) is more desirable than O(n log n) because one can increase the input size, and the growth rate will increase slower with the former than with the latter.

Just to express a complexity of an algorithm in a fast and simple way. The big O notation exist to explain the best, worst, and average-case time complexities for any given algorithm. There are just numerical functions over the size of possible problem instances.

In other way it is very difficult to work precisely with these functions, because they tend to:

• Have too many bumps – An algorithm such as binary search typically runs a bit faster for arrays of size exactly n = 2k − 1 (where k is an integer), because the array partitions work out nicely. This detail is not particularly significant, but it warns us that the exact time complexity function for any algorithm is liable to be very complicated, with little up and down bumps as shown in Figure 2.2.
• Require too much detail to specify precisely – Counting the exact number of RAM instructions executed in the worst case requires the algorithm be specified to the detail of a complete computer program. Further, the precise answer depends upon uninteresting coding details (e.g., did he use a case statement or nested ifs?). Performing a precise worst-case analysis like T(n) = 12754n2 + 4353n + 834lg2 n + 13546 would clearly be very difficult work, but provides us little extra information than the observation that “the time grows quadratically with n.”

It proves to be much easier to talk in terms of simple upper and lower bounds of time-complexity functions using the Big Oh notation. The Big Oh simplifies our analysis by ignoring levels of detail that do not impact our comparison of algorithms. The Big Oh notation ignores the difference between multiplicative constants. The functions f(n)=2n and g(n) = n are identical in Big Oh analysis

https://mimoza.marmara.edu.tr/~msakalli/cse706_12/SkienaTheAlgorithmDesignMan ual.pdf