COS 212
Complexity Analysis
Algorithm Complexity
The same problem can frequently be solved with
different algorithms which differ in efficiency
Some algorithms require more space than others
Technically, you could always buy more memory
Some require more time
No easy solutions here: even the fastest CPU has a limit
Time is usually a more important constraint
Algorithm time efficiency is measured in logical units
rather than real-time units such as “milliseconds per
byte of data”
Algorithm time efficiency is determined by the
relationship between the size n of data to be processed
and the amount of time t required to process the data
How do we determine ? How do we interpret ?
Interpreting f(n): Asymptotic Complexity
Suppose you manage to work out the relationship
f(n) between t and n (we’ll talk about how to do it
later)
Algorithm A: f(n) = 2n
t is double n
the relationship is linear
for 10 data units, you’ll need 20 time units
for 100 data units, you’ll need 200 time units
for 1000 data units, you’ll need 2000 time units
Algorithm B: f(n) =
t is n squared
the relationship is quadratic
for 10 data units, you’ll need 100 time units
for 100 data units, you’ll need 10,000 time units
for 1000 data units, you’ll need 1,000,000 time units
Which algorithm is more efficient?
Which one is more complex?
Asymptotic Complexity
Consider:
Algorithm C: f(n) = 2n +
Is it quadratic or linear?
Which term contributes more?
for 10 data units, you’ll need 120 time units
for 100 data units, you’ll need 10,200 time units
for 1000 data units, you’ll need 1,002,000 time units
dominates 2n
Which algorithm is more efficient: A (2n) or C?
A
Which algorithm is more efficient: B () or C?
Treat as equals
Why: because we only care about asymptotic
complexity, i.e. an approximation that describes the
order of complexity
How to determine asymptotic complexity:
Determine which term contributes the most
Discard the other terms!
Asymptotic Complexity: Big-O
How to determine order of complexity of f(n):
Determine which term contributes the most
Discard the other terms!
Paul Gustav Bachmann introduced the Big-O notation in
1894 to represent the asymptotic complexity of f(n):
• If f(n) is O(g(n)), then there are
O(g(n)) positive numbers c and N such
that f(n)cg(n) for all n N
What this basically means: f(n) grows at
most as fast as g(n), but never faster
g(n) is the “upper bound” of f(n)
What is O(g(n)) of f(n) = 2n ?
It is O(n)
Why? Because for any N, and c = 2, 2n 2n
Asymptotic Complexity: Big-O
c g(n)
f(n)
N n
Asymptotic Complexity: Big-O ❑ ❑
𝑙𝑜𝑔 𝑥=lg𝑥
2
1. f(n) =
Big-O: O()
2. f(n) = 1000000
Big-O: O()
3. f(n) = 2n +
Big-O: O()
4. f(n) = 10 + n + log n
Big-O: O(n)
5. f(n) = 10 + 364
Big-O: O()
What is that straight line at the bottom?
O(1), also referred to as constant complexity, describes
algorithms where execution time does not depend on the size of
the data structure (number of data units)
Big-O Properties
• If f(n) is O(g(n)) and g(n) is O(h(n)), then
1 f(n) is O(h(n))
• i.e., f(n) = O(g(n)) = O(O(h(n))) = O(h(n))
• If f(n) is O(h(n)) and g(n) is O(h(n)), then
2
f(n) + g(n) is O(h(n))
3 • ank is O(nk)
4 • nk is O(nk+j) for any j > 0
5 • If f(n) = c g(n), then f(n) = O(g(n))
6 • logan = O(logbn) for any numbers a, b > 1
7 • logan is O(log2n) for any positive a ≠ 1
Logarithm:
Calculating Big-O: examples
Now that you understand Big-O, let’s apply it to actual
algorithms
Count every assignment operation as “work” that
contributes to complexity
Example 1:
int i = 0, j = 1; // 2 assignments
while(i < n) {
i++; // assignment
j += 2; // assignment
}
How many assignments in total?
2 + 2n
What is the complexity?
O(n)
Calculating Big-O: examples
Example 2:
k = 0;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
k++;
How many assignments in total?
1 + 1 + n (1 + 1 + n(1 + 1))
Calculating Big-O: examples
Example 2: n
k = 0;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++) n
k++;
How many assignments in total?
1 + 1 + n (1 + 1 + n(1 + 1)) = 2 + 2n + 2
Complexity?
O()
Calculating Big-O: examples
Example 3:
for(i = 0; i < n; i++)
for(j = 0, sum = 0; j <= i; j++)
sum++;
1+2+…+𝑛=(𝑛(𝑛+1))/2
How many assignments in total?
n
1 + 3n +
= 1 + 3n + 2(1 + 2 + … + n)
= 1 + 3n + n(n + 1)
n
Complexity?
O()
Calculating Big-O: examples
Example 4:
for(i = 0; i < 10; i++)
for(j = 0; j < n; j++)
x += y;
How many assignments in total?
1 + 10(1 + 1 + n (1 + 1)) = 1 + 10(2 + 2n) = 21 + 20n
Complexity?
O(n)
Calculating Big-O: examples
Example 5:
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
for(k = 0; k < n; k++)
for(m = i-2; m <= i; m++)
x = i + j + k + m;
How many assignments in total?
1 + n(1 + 1 + n (1 + 1 + ()))
How many times will the innermost loop execute?
What is the Complexity?
O()
Calculating Big-O: examples
Example 6:
How many times will the
sum = 0, i = 9; while loop execute?
while(i < n) {
i++;
for(j = i – 8; j <= i; ++j)
sum++; How many times will the
for loop execute?
}
What is the Big-O
Complexity?
O(n)
Calculating Big-O: examples
Recursion:
How many times will the
int recursive(int n) recursive function
execute?
{
if (n <= 0)
return 1;
else
return 3 * recursive(n-1);
}
What is the Big-O
Complexity?
O(n)
Calculating Big-O: examples
Example 7:
Complexity is O()
int fib(n) {
if(n <= 1) return n; Is it good or bad?
else return fib(n-1) + fib(n-2);
}
It doesn’t get much
What is the complexity? worse than this!
Is it O(1 + O(n-1) + O(n-2))?
Calculating Big-O: examples
Example 8:
j = 5;
for(i = n; i >= 1; i/=2)
j *= j + i;
How many times does the loop execute?
i takes on values n/, n/,…, n/
We halve i every time till i < 1
Therefore, Logarithmic
n/ = 1 complexity: how many
Rewrite as times can you divide n
n= by a given base?
Now we can calculate m:
m=
(m is the total number of iterations)
Thus, O(lg n)