Visit
www.annedawson.net for more Computer Science Education resources
Last updated: Saturday 28th February
2009, 11:40 PT by AHD
Complexity of Algorithms Using BigOh
notation
A function f(n) is BigOh of a
function g(n) if:
there exists positive constants c
and n_{0} such that: f(n) <= c g(n) for n > n_{0}
O(1000n) = O(n)
O(n^{2} + 3n + 2) =
O(n^{2})
O(3n^{3} + 6n^{2}
 4n + 2) = O(3n^{3}) = O(n^{3})
If f(x) = n^{2} * log n = O(n^{2} logn)
Example 1
We can often analyze the running time of a
program by determining the number of times selected statements are executed. We
can usually get a good estimate of the running time by considering one type of
statement such as some statement in a for loop.
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cin >> A[i][j];
Number of times cin >> A[i][j]; executed: n^{2}
Complexity: O (n^{2})
Analysis: In a nested for loop with fixed lower and upper limits (e.g.
"0" and "n") the number of times the insider part is
executed is just n x n . f(n) = n^{2
}. So this program section
runs in O(n^{2}) time.
Example 2
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
A[i][j] = 0;
Analysis: This code zeroes out the lower
triangular part of a twodimensional array. Since the inner loop is executed a
variable amount of times, we can't just multiply n by i:
When i = 0 the inner loop is
executed 0 times.
When i = 1 the inner loop is executed 1 time.
When i = 2 the inner loop is executed 2 times.
So the number of times the statement "A[i][j] = 0" is executed is: 1
+ 2 + 3 + ... + n
This sum comes up a lot in algorithm analysis. You should memorize the formula:
1 + 2 + 3 + ... + n = n(n+1)/2
= 1/2(n^{2 }+ n)
Since in BigOh analysis we ignore leading constants (the 1/2 in the equation above) and lower order terms (the n in the equation above), this algorithm runs in O(n^{2}) time.
Example 3
Dim iSum,i,j,k As Integer
For i = 1 to n
For j = 1 to
n
iSum = iSum
+ 1  = 1 x n
Next j
For k = 1 to 2 *
n
= x n
iSum =
iSum + 1

iSum =
iSum + 1
 = 3 x 2n
iSum =
iSum + 1

Next k
Next i
Number of times executed: n x (1 x n + 3 x 2n) = n^{2} + 6n^{2}
= 7n^{2}
Complexity: O (n^{2})
Since in BigOh analysis we ignore leading constants (the 7 in the equation above), this algorithm runs in O(n^{2}) time.
Example 4
Dim iSum,i,j,k As Integer
For i = 1 to n
For j = 1 to n
iSum = iSum + 1 = 1 x n
Next j
For k = 1 to 2 * n = x n
iSum = iSum + 1 = 1
For m = 1 to 4 * n step 2 = 2n
iSum = iSum + 1 = 1 x 2n
Next m
Next k
Next i
Number of times executed: n (1 x n + 2n (1 + (1 x 2n)))
= n (n + 2n (1 + 2n))
= n (n + 2n + 4n^{2})
= n^{2} + 2n^{2} + 4n^{3}
= 3n^{2} + 4n^{3}
Complexity: O (n^{3})
Since in BigOh analysis we ignore leading constants (the 3 and 4 in the equation above)
and lower order terms (the n^{2} in the equation above), this algorithm runs in O(n^{3}) time.
Example 5
void main(void)
{
int i, tofind, A[100], n;
i = 0;
cin >> tofind;
while ((A[i] != tofind) && (i < n)) i++;
if (i > n) cout << "not found";
else cout << "found";
}
Analysis: This code has a comparision: (A[i] != tofind) . We count comparisons to determine the
running time. This means the running time is essentially the number of times
the while loop is executed. This depends on the input and the value of tofind which we do not know. So we must consider the worst possible case. In
the worst case the value of tofind is not found and the while loop is executed n times. Therefore the
worstcase running time is O(n).
Example 6
All the previous examples have been actual
code. You should be able to analyze pseudocode too, although this can be
tricky because pseudocode is more vague. In pseudocode the last example above
would be:
search the array starting from location 0
comparing each element to the search value until it is either found
or the end of the array is reached.
Analysis: The worstcase will be when the
search value is not found and is compared to every element of the array. If
there are n elements this takes O(n) time.
Example 7
Some algorithms have logarithmic
(base 2) complexity:
1. i = n; // i starts from n
2. while (i >= 1)
3. {
4. x = x + 1; // count this line
5. i = i / 2; // i becomes half at the end of every iteration
6. }
iteration 
value of i 
number of times 
1 
n 
1 
2 
n/2^{1} 
^{1} 
3 
n/2^{2} 
^{1} 
k 
n/2^{k1} = 1 
1 
k+1 
n/2^{k} = 0 
0 
We are interested in what k is
(because that's the number of times the line 4 is executed). In other
words,
T(n) = 1 + 1 + 1 + .. + 1 = (k
* 1)
< k of
them>
To derive k, we look at the relation
at the last iteration (kth):
So, T(n) = log_{2}n + 1 (where log_{2}n is
alternatively written as log n).
Common
asymptotic growth functions (complexity classes) in an ascending order:
T(n) 
Name 
1 
constant 
log n 
logarithmic 
n 
linear 
n log n 
n log n 
n^{2} 
quadratic 
n^{3} 
cubic 
n^{m} 
(general) polynomial (m is a fixed, nonnegative integer; ; e.g. n^{4}, n^{5}) 
m^{n} 
exponential (m >= 2; ; e.g. 2^{n}, 3^{n}) 
n! 
factorial 