Asymptotic Notations - Big Oh

Software Development
#1

Big-Oh notation pronounced as big o, is the upper bound of a function is denoted as capital O.

Definition: Suppose we have two functions f(n) and g(n), then the function f(n) = O(g(n) if and only if there exists two positive constants c and k, such that f(n) <= c * g(n) for all n >= k

For example:

Suppose, if f(n) = 2 * n + 3, then

2 * n + 3 <= 5 * n for all n >= 1.

In the above equation,
c = 10, k = 1, and g(n) = n

Now we know that, n < n log(n) < n^2 < n^3 < — < 2^n < 3^n <---- n^n.
In the above comparison, n log(n), n^2, n^3, —, 2^n, 3^n, —, n^n are upper bound.

This symbolizes,

  1. f(n) = O(n) — True
  2. f(n) = O(n^2) — True
  3. f(n) = O(3^n) — True, and so on…

Finally, in Big-Oh, we take the the nearest g(n), which in this case is O(n).

#2
Properties of Asymptotic Notations
#3

The video does explain a few basic procedural and technical ideas, which are important, but I don’t think you get the big picture from it. The big picture is this:

Take the task of searching a database. The worst algorithms are generally O(n); the best are generally O(log n). Let me explain the practical significance.

For O(n):

If it takes 1 second to search a thousand records, then it takes a million seconds to search a million records, and it takes 100 million seconds to search a 100 million records. Simple, huh?

But that’s disastrous. If you’re developing a database to check 100 million credit records, then a search time of 100 million seconds is beyond horrible. It would mean that to access John Smith’s credit report, the retrieval time would be thousands of hours. That is absolutely unacceptable.

For O(log n):

But now we have a different situation. O(log n) means that search time increases as the inverse of exponentiation… Exponentiation is fast, explosive. Logarithms, therefore, are the absolute opposite. It means that as N increases exponentially, Log N increases very very slowly. So……

IF it takes 1 second to search a thousand records, THEN

It takes 2 sconds to search a million records,

It takes 3 second to search a billion records,

And it takes 4 seconds to seach a trillion records.

Let’s say that we “only” need to search a billion records. Because of logarithmic growth in the time required, this means that N may grow exponentially while time required increases slowly — in linear amounts.

So insted of needing thousands of hours, we need only 3 seconds for a Database search.

Yet the situation is in some sense better than that. Increases in time required from 1 to 3 to 5 seconds are usually easy for the engineers to handle. Remember that chips are getting faster all the time, a la Moore’s law. So if something takes 5 seconds today, we can expect execution to someday take < 1 second.

That being the case, we can eventually expect a trillion-record search to be very responsive. Some day we should expect access time to easily be 5 times faster, thanks to Moore’s Law. That’s easy.

With the combined virtues of Moore’s Law, along with logmarithmic growth in search time — which is what O(log n) menas — the ability to search literally astronomical numbers of records in less than a second becomes doable.

#4