Understanding Big-O Notation

Question

I am reading a book "Beginning Algorithms" by Simon Harris and James Ross.

In the early pages, there is a section on Understanding Big-O Notation. I read this section, and re-read this section maybe about a dozen times. I still am not able to wrap my head around a couple of things. I appreciate any help to get rid of my confusion.

The author / authors state "The precise number of operations is not actually that important. The complexity of an algorithm is usually defined in terms of the order of magnitude of the number of operations required to perform a function, denoted by a capital O for order of followed by an expression representing some growth relative to the size of the problem denoted by the letter N."

This really made my head hurt, and unfortunately, everything else following this paragraph made no sense to me because this paragraph is supposed to lay the foundation for the next reading.

The book does not define "order of magnitude." I googled this and the results just told me that order of magnitude are defined in powers of 10. But what does that even mean? Do you take the number of operations and define that number in a power of 10, and that equals the complexity? Also, what is considered the "size of the problem?" Is the size of the problem the number of operations? Or is the size of the problem the "order of magnitude of the number of operations required to perform a function."

Any practical examples and a proper explanation of this would really help.

Thanks!

Answer 1

Keep it simple!

Just think of the Big-O as a way to express the performance of the algorythm. That performance will depend on the number of elements the algorythm is handeling = n.

An example, when you have to make a sum. You need one statement for the first addition, one statement for the second addition, and so on... So the performance will be linear with the number of elements = O(n).

Imagine a sort algorythm, which is very smart, and for each element of handles it automatically shortens the sort for the next element. This will be logarithmic with the number of elements = O(log(n)).

Or a complex formula with parameters, and with each extra parameter, the execution time multiplies. This will be exponential = O(10^n).