BRONX COMMUNITY COLLEGE

of the City University of New York

DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE

CSI 33 Section E01 Handout 1

Fall 2014 September 3, 2014

Big O Notation for Time Complexity of Algorithms

Time depends on size of the data
When working with a significant amount of data, the time it takes to process it will of course depend
on how much data there is. As the data size increases, some algorithms will eventually be faster than
others (even though they may be performing the same task, such as sorting an array). Here are some
simple examples of Python functions which have running time t which depends on n, the size of the
data set being processed (the number of individual data items). We can express this relation between
running time and data size, using function notation, as t = f (n).
In all cases, the function takes a single parameter a which is a Python list. A Python list is
implemented as an array of data references; if the length of the list is n, then there are n data items in
the list.

A constant time algorithm

For our first example, the single line of code in the body of the function is executed once, and the
function returns.
function0(a)
{
a[0] = 0;
}

The running does not depend on the array size here; if the time it takes to run the fixed block of
code is k0 , the the formula for the running time is t = k0 . In a graph of the function f (n) = k0 , we can
see that if the size n increases arbitrarily, the running time remains constant; only the first element of
the array is ever used.
t

1
A linear time algorithm
For our second example, the body of the function consists of a loop which executes n times.

function1(a)
{
n = len(a)
for i = 0; i < n; i++
a[i] = 0;
}

So the function will take longer if the size of the array is larger, in direct proportion: t = k1 n, where k1
is the time it takes to run the code in the loop once. The graph of the function f (n) = k1 n is a straight
line through the origin whose slope is k1 .
t

Comparing any linear function with a constant function shows that the constant function is eventually
faster, since the value of t stays constant, while in the linear function it always increases as n gets larger.
t

2
A quadratic (n2 ) time algorithm
For our third example, the body of the function consists of a loop which executes n times. But nested
within this loop is another loop which also executes n times. The code in the inner loop runs n times for
each time the outer loop runs. Since the outer loop also has n iterations, the inner code must execute
n2 times. So the function will take n2 times the length of time it takes to run the inner loop once. If
the time to run the inner loop once is k2 , the formula for running time is t = k2 n2 .

function2(int a)
{
for (i = 0; i < n; i++)
for (j = 0; i < n; j++)
a[i][j] = 0;
}

The graph of this quadratic function takes the shape of a parabola.

t

Comparing this graph with a linear function, we see that the quadratic function is not as good as linear:
eventually, any linear function will lie below the parabola, meaning time t is smaller for large enough
data size n.
t

3
A cubic (n3 ) time algorithm
For our next example, the body of the function consists of a loop which executes n times, with two levels
of nesting of inner loops, each iterating n times. But nested within this loop is another loop which also
executes n times. The function will take n3 times the length of time it takes to run the inner loop once,
that is, if the time to run the inner loop once is k3 , the formula for running time is t = k3 n3 .

function3(int a)
{
for (i = 0; i < n; i++)
for (j = 0; i < n; j++)
for (k = 0; i < n; k++)
a[i][j][k] = 0;
}

If we were to graph this function, it would have the typical shape of a cubic function, increasing more
rapidly than any quadratic function. In fact, in comparing any polynomial functions, it is only the term
of highest degree which matter. The graph of any quadratic function (with degree 2) will always be a
parabola, so the function will eventually be less than any polynomial of degree 3.

A logarithmic time algorithm

The next example is a recursive algorithm to perform a binary search of a sorted array to find a specific
value (from the text, page 580, but with the parameter size changed to n) to follow the other examples:

# bsearch.py
def search(items, target):

pre: items is a **sorted** list of numbers
post: returns non-negative x where items[x] == target, if target in
items; returns -1, otherwise

low = 0
high = len(items) - 1
while low <= high: # There is still a range to search
mid = (low + high) // 2 # position of middle item
item = items[mid]
if target == item : # Found it! Return the index
return mid
elif target < item: # x is in lower half of range
high = mid - 1 # move top marker down
else: # x is in upper half
low = mid + 1 # move bottom marker up
return -1 # no range left to search,
# x is not there

To simplify the analysis, assume that the size, n, is always a power of 2. Each recursive call to search
divides n by two, reducing n by one power of two. In other words, the logarithm to base two of m
decreases by one. So the maximum number of calls will be the number needed to reduce the logarithm
of n to zero. This will take log2 (n) recursive calls, with each call taking a constant time. This analysis
reveals that the time to perform this function is, on average, proportional to the logarithm (base 2) of
n: t = klog2 (n). From precalculus, recall that changing the base of the logarithm changes the constant,
but it is still some constant. So the important part of the function is that it is a logarithm, and all such

4
functions have the usual shape, multiplied by some constant: t = k log2 (n).
t

Comparing this graph with any linear function, we see that O log(n) is an improvement over O(n),
since it is eventually faster.
t

Big O Notation
All constant functions have the form f (n) = k0 = k0 1. They all have the property that they are
eventually faster than linear functions, which have the form f (n) = k1 n + k0 . We express this by saying
that O(1), the class of constant functions, is eventually less than the class of O(n), the class of linear
functions. We write this as O(1) < O(n). There is a hierarchy, or ordering, of the running times of
different kinds of algorithms based on what big-O class they are in:
O(1) < O(n) < O(n2 ) < O(n3 ) and so on; here a < b means ba is eventually faster than b. We
have also seen that O(1) < O(log(n)) < O(n). This means that any O(1) function f0 (n) = k0 is
eventually less than any O(log(n)) function f (n) = k1 log(n), which is eventually less (faster) than any
O(n) function f (n) = k1 n + k0 .
Another way of saying this is that there is some n such that, for all m > n, k0 < k1 log(m) < k2 m.
Playing with these inequalities, we multiply them by m, which is greater than zero, so it does not change
the direction of the inequalities:
eventually, k0 m < k1 m log(m) < k2 m2 . So we know that O(n) < O(n log(n)) < O(n2 ). This gives more

5
information about which algorithms are fastest: O(1) < O(log(n)) < O(n) < O(n log(n)) < O(n2 ), and
so on.
Different sorting algorithms are known to have different complexities. Bubblesort, insertion sort
and selection sort all have time complexity of O(n2 ), since these are loops within loops. Quicksort
and heapsort have complexity O(n log(n)), because they are recursive, and divide the sorting problem
roughly in half for each stage of the iteration.

Other considerations when comparing algorithms

When one algorithm has the same big-O as another, you must look at other issues, like what are the
constants to the functions. A smaller constant (a smaller or faster inner body of code) will make the
algorithm with the smaller constant the better choice.
If a member function for an abstract data type is going to be used with more frequency than another
function, then the time complexity (big-O) of the algorithm which it uses is more important than the
big-O of the other function. Conversely, if a member function is rarely used, it can use a less time-efficient
algorithm than a function which is used more often.
If the size of the data will be known to be below a certain value, then the constants in the time
formulas become more important than the exponents, since the application may be in the part of the
graph where the higher big-O function is still below the lesser big-O function. The latter function only
wins eventually, but for small values of n this may not happen.
Different sorting algorithms are chosen on this basis. If you are sorting a list of less than, say, 10
items, a bubble sort (O(n2 )) may work as well as quicksort (O(n log(n)). But if you are sorting a
database of the entire U.S. population (over 3 million), the best option is the most efficient algorithm
possible: here, heapsort or quicksort would be used instead of insertion sort or selection sort, for example.