Big O Notation is used to describe the relationship between the size of the input and the running time of the algorithm. It is a crucial factor to look at when we need to evaluate the efficiency/performance of an algorithm.

Big O Notation is denoted by the syntax O(expr). The expression inside is usually in terms of n, where n is the size of the input.

To figure out the complexity of a given algorithm:

For example, suppose a program does:

        1. print out all of the letters of an input string

        2. print out the string "apple"

The equations to represent the complexity of each line would be

    1. time to print a single letter * the length of the input string

    2. time to print a single letter * the length of "apple" which is 5

Given that the time it takes to print a single letter is the constant t, Step 1 takes t * n time where n is the length of the input string, which experiences a linear growth as the length of the input increases (O(n)). While Step 2 takes t * 5, which remains constant no matter how big the input size is (O(1)). Hence we consider Step 1 to have a greater growth rate than Step 2. Considering the two steps as functions of n, this process is essentially examining the asymptotic behaviors of the two functions.

As a result of this, the expression to represent the complexity for this algorithm would be t * n, however, since t is a constant, it should be omitted.

Hence, the time complexity is denoted as O(n).