Sunday, March 1, 2015

Big O Notation

Alright so we can't dive too deeply into performance without having some knowledge about big O notation. Let's get something out of the way first- the "O" in big O notation comes from the upper-case, greek omicron. This is used in mathematics and represents the asymptotic rate of growth of a function when the argument tends towards a particular value or infinity. To put it simply, in software, big O notation aims to assess the complexity of a function or algorithm.

To define this mathematically, we can write out the following:

if ∃ constants a,b > 0 such that
f(n) ≤ a * g(n) ∀ n ≥ b
then f(n) = O(g(n))

This reads as "If there exists constants a and b greater than 0 such that f(n) is less than or equal to a times g(n) for all n greater than b, then f(n) equals O(g(n))." If that's still a bit hard to grasp, we can represent the same information as the following graph:

As you can see, f(n) grows linearly, while a * g(n) grows exponentially. Now, the y axis represents the operational cost and the x axis is the size of the input. So from here, f(n) is always less than or equal to a * g(n) for every input n greater than the point b. In other words, after point b, a * g(n) is more expensive.

Calculating Cost

So moving on, big O looks like this: O(n). O is a function and different values can be passed into it.

Constant Time

With O(1) operations, the input size is irrelevant. The amount of time for the operation to run is the same. Take the following examples:

# example 1
x = 1

# example 2
def get_item(index, data):
  return data[index]

# example 3

In the following graph, we have 2 constants being represented where the operation cost stays the same.

Linear Complexity

With O(n) operations, the input size has a direct correlation to the cost. As the size of the input grows, the cost grows linearly, along with it. An example would be a function that adds up all of the elements of an array.

def iterate_list(data):
  result = 0                    # O(1) step 1
  for item in data:             # O(n) step 2
    result += data[item]        # O(1) step 3
  return result                 # O(1) step 4

Now, let's break down each step. We'll start by defining f(n).

number_of_steps = f(n)
number_of_steps = f(data.length)

Next, we're going to add every step of our function that doesn't depend on the size of the array, represted by C as in constant. Steps 1 and 4 both take C steps each, so we end up with:

f(n) = C + ? + C

Then, we represent the for loop with the following:

f(n) = C + (C + C + ... + C) + C
f(n) = C + n * C + C

We simplify the loop by representing it with n, disregarding variable initialization, condition and incrementation step.

Now, to get the actual big O, we'll need an asymptotic analysis of our function by performing the following steps:

  1. Take away all the constants C and redundant parts
  2. Get the polynomium in its standard form from f()
  3. Divide the terms of the polynomium and sort them by the rate of growth
  4. Keep the one that grows bigger when n approaches infinity

Keep in mind, we want to express how cost changes in rough terms, not offer a precise calculation. We take away the constants because their impact on the number of operations can become insignificant as the input size grows. We're also considering the worst case scenarios of an algorithm, which we'll explain in more detail in the next section. So, we end up with O(n).

In the following graph, we can see where our linear operations become more expensive than our constant operations at the point the lines intersect. So 5x + 4 is cheaper than our constant up until the input size is greater than 4.

Quadratic Complexity

With O(n²) operations, the complexity grows exponentially as the size of the input increases. A perfect, every day example of this is the basic multiplication of two numbers on paper. Take a look at the following:

x   958

So we lined the numbers up, took the first digit of the bottom number and multiplied it against every digit of the top number. And we repeated this with every one of the bottom numbers. So to multiply two 3 digit numbers, we had to perform 9 operations. Two 4 digit number would cost 16 operations and so on. Now, there will be cases where you're going to multiple a 4 digit number with, say, a 2 digit number. As far as big O is concerned, we still treat this as O(n²), as if both numbers were 4 digits because, like we mentioned earlier, we're concerned with the worst case scenario.

When programming, the most common example of O(n²) is the nested for loop:

def get_pairs(lst):
  pair_list = []                    O(1)
  for i1 in lst:                    O(n)
    for i2 in lst:                  O(n)
      pair_list.append([i1, i2])    O(1)
  return pair_list                  O(1)

Now, let's break this down so we can graph it:

f(n) = O(n) * O(n) + O(1) + O(1) + O(1)
f(n) = O(n²) + O(1) + O(1) + O(1) + O(1)
f(n) = x² + 6 + 4 + 3 # replace n with x and put in arbitrary constants
f(n) = x² + 13

Now compared with an O(n) operation, you can see how costly O(n²) is, especially with a large data set.

Logarithmic Complexity

O(log n) operations are more efficient when dealing with really large inputs. So what exactly is a logarithmic algorithm? Well if you've ever been to a library or sifted through the pages of a phone book, you've already performed this algorithm, yourself, in the form of a binary search. You start with your search term (last name) and a data set (phone book), and flip to an arbitrary page. Comparing the name you're looking for to the names on the page, you will either flip to an earlier page or a later page. You repeat this process, dividing your data set in half each time, until you locate your target.

  • So worst case scenario, a data set of 3 names costs 2 operations.
  • 7 names cost 3
  • 15 costs 4.
  • And 1,000,000 costs 20.

As you can see, this is extremely efficient with large inputs. Let's see how O(log n) algorithm compare to our other algorithms.


Now, that we have a pretty good understanding of this process, let's wrap up by going over some caveats. First, when computing the performance of an algorithm, you have to keep in mind that we're producing a theoretical barometer, not a practical one. In reality, sometimes, it doesn't matter how big the list is. Sometimes, constant operations end up being slower that the O(n²) operations.

Secondly, this probably isn't going to make your application run faster because most of its operations will be bottlenecked by I/O calls like fetching or writing to a database. There's more to gain when applying this to CPU-bound operations (gaming, simulations, etc).

No comments:

Post a Comment