Programming and Algorithms

CSE308
LECTURE 6: TIME COMPLEXITY

BY: DR. MOSTAFA ABDELRAZIK

 Measuring Efficiency

The efficiency of an algorithm is a measure of the amount of resources

consumed in solving a problem of size n.
◦ The resource we are most interested in is time
◦ We can use the same techniques to analyze the consumption of other resources, such
as memory space.

It would seem that the most obvious way to measure the efficiency of an
algorithm is to run it and measure how much processor time is needed

Is it correct ?

2
 Factors

 Hardware

 Operating System

 Compiler

 Size of input

 Nature of Input

 Algorithm

Which should be improved?

3
 Good Algorithms?

Run in less time

Consume less memory

But computational resources (time complexity) is usually more

important

4
 Analysis of algorithms
Issues:
◦ correctness
◦ time efficiency
◦ space efficiency
◦ optimality

Approaches:
◦ empirical analysis – less useful
◦ theoretical analysis – most important

5
 Empirical analysis of time
efficiency
Select a specific sample of inputs

Use physical unit of time (e.g., milliseconds) or

Count actual number of basic operation’s executions

Analyze the empirical data

Problems:

6
 Empirical analysis of time
efficiency
Select a specific sample of inputs

Use physical unit of time (e.g., milliseconds) or

Count actual number of basic operation’s executions

Analyze the empirical data

Problem - Inefficient:
◦ Must implement algorithm
◦ Must run on many data sets to see effects of scaling
◦ Hard to see patterns in actual data

7
 Theoretical analysis of time
efficiency
Time efficiency is analyzed by determining the number of repetitions of the
basic operation as a function of input size

Basic operation: the operation that contributes most towards the running time
of the algorithm

input size

T(n) ≈ copC(n)
running time execution time Number of times
for basic operation basic operation is
executed
8
 RUNNING TIME OF AN ALGORITHM

Depends upon
◦ Input Size
◦ Nature of Input

Generally time grows with size of input, so running time of an

algorithm is usually measured as function of input size.

Independent from machine, OS

9
 RUNNING TIME OF AN ALGORITHM

Running time is measured by number of steps/primitive

operations performed

Steps means elementary operation like

+, *,<, =, A[i] etc

We will measure number of steps taken in term of size of input

10
 Input size and basic operation
examples
Problem Input size measure Basic operation

Searching for key in Number of list’s items,

Key comparison
a list of n items i.e. n

Matrix dimensions or
Multiplication of two Multiplication of
total number of
matrices two numbers
elements

n’size = number of
Checking primality
digits (in binary Division
of a given integer n
representation)

11
 Simple Example

// Input: int A[N], array of N integers

// Output: Sum of all numbers in array A
int Sum(int A[], int N)
{
int s=0;
for (int i=0; i< N; i++)
s = s + A[i];
return s;
}
How should we analyse this?

12
 Simple Example

// Input: int A[N], array of N integers

// Output: Sum of all numbers in array A
int Sum(int A[], int N){
int s=0; 1
for (int i=0; i< N; i++)
2 3 4
s = s + A[i];
5 1,2,8: Once
return s;
6 7
3,4,5,6,7: Once per each iteration
}
8 of for loop, N iteration
Total: 5N + 3
The complexity function of the
algorithm is : f(N) = 5N +3

13
 Simple Example Growth of 5n+3

Estimated running time for different values of N:

N = 10 => 53 steps
N = 100 => 503 steps
N = 1,000 => 5003 steps
N = 1,000,000 => 5,000,003 steps

As N grows, the number of steps grow in linear proportion to N for this function
“Sum”

14
 What Dominates in Previous Example?

What about the +3 and 5 in 5N+3?

◦ As N gets large, the +3 becomes insignificant
◦ 5 is inaccurate, as different operations require varying amounts of time and also
does not have any significant importance

What is fundamental is that the time is linear in N.

Asymptotic Complexity: As N gets large, concentrate on the

highest order term:
◦ Drop lower order terms such as +3
◦ Drop the constant coefficient of the highest order term i.e. N

15
 Asymptotic Complexity

The 5N+3 time bound is said to "grow asymptotically" like N

This gives us an approximation of the complexity of the algorithm

Ignores lots of (machine dependent) details, concentrate on the bigger

picture

16
COMPARING FUNCTIONS: ASYMPTOTIC NOTATION

Big Oh Notation: Upper bound

Omega Notation: Lower bound

Theta Notation: Tighter bound

17
 Big Oh Notation [1]

If f(N) and g(N) are two complexity functions, we say

f(N) = O(g(N))

(read "f(N) is order g(N)", or "f(N) is big-O of g(N)")

if there are constants c and N0 such that for N > N0,
f(N) ≤ c * g(N)
for all sufficiently large N.

18
Big Oh Notation [2]

19
t(n)  O(g(n)) iff t(n) <=cg(n) for n > n0

t(n) = 10n3 in O(n3) and in O(n5). What c and n0? More later.
20
O(f(n))

21
 Example (2): Comparing Functions

4000

Which function is better? 3500

10 n2 Vs n3 3000

2500

10 n^2
2000
n^3

1500

1000

500

0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

22
 Comparing Functions

As inputs get larger, any algorithm of a smaller order will be more

efficient than an algorithm of a larger order

0.05 N2 = O(N2)
Time (steps)

3N = O(N)

Input (size)
N = 60

23
 Big-Oh Notation

Even though it is correct to say “7n - 3 is O(n3)”, a better statement is “7n - 3

is O(n)”, that is, one should make the approximation as tight as possible

Simple Rule:
Drop lower order terms and constant factors
7n-3 is O(n)
8n2log n + 5n2 + n is O(n2log n)

24
 Big Omega Notation

If we wanted to say “running time is at least…” we use Ω

Big Omega notation, Ω, is used to express the lower bounds on a function.

If f(n) and g(n) are two complexity functions then we can say:
f(n) is Ω(g(n)) if there exist positive numbers c and n0 such that 0<=f(n)>=cΩ (n) for all n>=n0

25
t(n)  Ω(g(n)) iff t(n) >=cg(n) for n > n0

t(n) = 10n3 in Ω(n2) and in Ω(n3)

26
 Big Theta Notation

If we wish to express tight bounds we use the theta notation, Θ

f(n) = Θ(g(n)) means that f(n) = O(g(n)) and f(n) = Ω(g(n))

27
 t(n) Θ(g(n)) iff t(n)O(g(n)) and
Ω(g(n))

t(n) = 10n3 in Θ(n3) but NOT in Θ(n2) or Θ(n4)

28
 What does this all mean?

If f(n) = Θ(g(n)) we say that f(n) and g(n) grow at the same rate,
asymptotically

If f(n) = O(g(n)) and f(n) ≠ Ω(g(n)), then we say that f(n) is asymptotically
slower growing than g(n).

If f(n) = Ω(g(n)) and f(n) ≠ O(g(n)), then we say that f(n) is asymptotically
faster growing than g(n).

29
 Which Notation do we use?

To express the efficiency of our algorithms which of the three notations

should we use?

As computer scientist we generally like to express our algorithms as big

O since we would like to know the upper bounds of our algorithms.

Why?

If we know the worse case then we can aim to improve it and/or avoid
it.

30
 Size does matter[1]

What happens if we double the input size N?

N log2N 5N N log2N N2 2N
8 3 40 24 64 256
16 4 80 64 256 65536
32 5 160 160 1024 ~109
64 6 320 384 4096 ~1019
128 7 640 896 16384 ~1038
256 8 1280 2048 65536 ~1076

31
 Complexity Classes
Time (steps)

32
 Size does matter[2]

Suppose a program has run time O(n!) and the run time for
n = 10 is 1 second

For n = 12, the run time is 2 minutes

For n = 14, the run time is 6 hours

For n = 16, the run time is 2 months

For n = 18, the run time is 50 years

For n = 20, the run time is 200 centuries

33
 Standard Analysis Techniques

Constant time statements

Analyzing Loops

Analyzing Nested Loops

Analyzing Sequence of Statements

Analyzing Conditional Statements

34
 Constant time statements

Simplest case: O(1) time statements

Assignment statements of simple data types
int x = y;
Arithmetic operations:
x = 5 * y + 4 - z;
Array referencing:
A[j] = 5;
Array assignment:
 j, A[j] = 5;
Most conditional tests:
if (x < 12) ...

35
 Analyzing Loops[1]

Any loop has two parts:

◦ How many iterations are performed?
◦ How many steps per iteration?

int sum = 0,j;

for (j=0; j < N; j++)
sum = sum +j;

◦ Loop executes N times (0..N-1)

◦ 4 = O(1) steps per iteration

Total time is N * O(1) = O(N*1) = O(N)

36
 Analyzing Loops[2]

What about this for loop?

int sum =0, j;
for (j=0; j < 100; j++)
sum = sum +j;

Loop executes 100 times

4 = O(1) steps per iteration

Total time is 100 * O(1) = O(100 * 1) = O(100) = O(1)

37
 Analyzing Loops – Linear Loops

Example (have a look at this code segment):

Efficiency is proportional to the number of iterations.

Efficiency time function is :
f(n) = 1 + (n-1) + c*(n-1) +( n-1)
= (c+2)*(n-1) + 1
= (c+2)n – (c+2) +1
Asymptotically, efficiency is : O(n)
38
 Analyzing Nested Loops[1]

Treat just like a single loop and evaluate each level of nesting as needed:

int j,k;
for (j=0; j<N; j++)
for (k=N; k>0; k--)
sum += k+j;
Start with outer loop:
◦ How many iterations? N
◦ How much time per iteration? Need to evaluate inner loop

Inner loop uses O(N) time

Total time is N * O(N) = O(N*N) = O(N2)

39
 Analyzing Nested Loops[2]

What if the number of iterations of one loop depends on the counter of the other?

int j,k;
for (j=0; j < N; j++)
for (k=0; k < j; k++)
sum += k+j;

Analyze inner and outer loop together:

Number of iterations of the inner loop is:

0 + 1 + 2 + ... + (N-1) = O(N2)

40
 How Did We Get This Answer?

When doing Big-O analysis, we sometimes have to compute a series like: 1 + 2 + 3 +

... + (n-1) + n

i.e. Sum of first n numbers. What is the complexity of this?

Gauss figured out that the sum of the first n numbers is always:

41
 Sequence of Statements

For a sequence of statements, compute their complexity functions individually

and add them up

Total cost is O(n2) + O(n) +O(1) = O(n2)

42
 Conditional Statements

What about conditional statements such as

if (condition)
statement1;
else
statement2;
where statement1 runs in O(n) time and statement2 runs in O(n2) time?
We use "worst case" complexity: among all inputs of size n, what is the maximum
running time?
The analysis for the example above is O(n2)

43
 Deriving A Recurrence Equation

So far, all algorithms that we have been analyzing have been non recursive
Example : Recursive power method

If N = 1, then running time T(N) is 2

However if N ≥ 2, then running time T(N) is the cost of each step taken plus time required to
compute power(x,n-1). (i.e. T(N) = 2+T(N-1) for N ≥ 2)
How do we solve this? One way is to use the iteration method.

44
 Iteration Method

This is sometimes known as “Back Substituting”.

Involves expanding the recurrence in order to see a pattern.
Solving formula from previous example using the iteration method :
Solution : Expand and apply to itself :
Let T(1) = n0 = 2
T(N) = 2 + T(N-1)
= 2 + 2 + T(N-2)
= 2 + 2 + 2 + T(N-3)
= 2 + 2 + 2 + ……+ 2 + T(1)
= 2N + 2 remember that T(1) = n0 = 2 for N = 1
So T(N) = 2N+2 is O(N) for last example.
45
 Asymptotic order of growth
Critical factor for problem size n:
- IS NOT the exact number of basic ops executed for given n
- IS how number of basic ops GROWS as n increases

- Constant factors and constants do not change growth RATE

- Rate most relevant for large input sizes, so ignore small sizes
- Informally: 5n^2 and 100n^2 +1000 are both n^2
- Define formally later

Call this: Asymptotic Order of Growth

46
Answer these questions

Running time T(n) Complexity O(n)

n2 + 100 n + 1
0.001n3 + n2 + 1
23 n
23n
23+n
23n
47
 Answer these questions
Running time T(n) Complexity O(n)
n2 + 100 n + 1 O(n2)
0.001n3 + n2 + 1 O(n3)
23 n O(n)
23n O(8n) as 23n(23)n
23+n O(2n) as 23+n232n
23n O(3n)
48
 Answer these questions

Running time T(n) Complexity O(n)

0.0001 n + 10000
100000 n + 10000
0.0001 n2 + 10000 n
100000 n2 + 10000 n
30 log20(23n)
actually NOT that hard…
49
 Answer these questions

Running time T(n) Complexity O(n)

0.0001 n + 10000 O(n)
100000 n + 10000 O(n)
0.0001 n2 + 10000 n O(n2)
100000 n2 + 10000 n O(n2)
30 log20(23n) O(log n) as
actually NOT that hard… logc(ab)=logca +logcb
50
 Time complexity growth
f(n) Number of data items processed per:
1 minute 1 day 1 year 1 century
n 10 14,400 5.26106 5.26108
n log n 10 3,997 883,895 6.72107
n1.5 10 1,275 65,128 1.40106
n2 10 379 7,252 72,522
n3 10 112 807 3,746
2n 10 20 29 35
51
 Growth rate: critical for performance performance

Focus: asymptotic order of growth:

Main concern: which function describes behavior.
Less concerned with constants
52
 Best-case, average-case, worst-case
For a given input size, how does algorithm perform
on different datasets of that size
For datasets of size n identify different datasets that give:
Worst case: Cworst(n) – maximum over all inputs of size n
Best case: Cbest(n) – minimum over all inputs of size n

Average case: Cavg(n) – “average” over inputs of size n

◦ Typical input, NOT the average of worst and best case
◦ Aanalysis requires knowing distribution of all possible inputs of size n
◦ Can consider ALL POSSIBLE input sets of size n, average over all sets

Some algs are same for all three (eg all case performance)
53
 Example: Sequential search

Worst case
Best case
Average case: depends on assumputions about input: ?
54
 Example: Sequential search

Worst case
Best case
Average case: depends on assumputions about input: proportion of found vs not-
found keys
55
 Critical factor for analysis: Growth rate

Most important: Order of growth as n→∞

◦ What is the growth rate of time as input size increases

◦ How does time increase as input size increases

56
 Order of growth: Upper, tight, lower bounds

More formally:
- Θ(g(n)): class of functions f(n) that grow at same rate as g(n)

Upper, tight, and lower bounds on performance:

O(g(n)): class of functions f(n) that grow no faster than g(n)
◦ [ie f ’s speed is same as or faster than g, f bounded above by g]

Θ(g(n)): class of functions f(n) that grow at same rate as g(n)

Ω(g(n)): class of functions f(n) that grow at least as fast as g(n)

◦ [ie f ’s speed is same as or slower than g, f bounded below by g]

57
Basic asymptotic efficiency classes
1 constant Best case
log n logarithmic Divide
Ignore part

n linear Examine each

Online/Stream Algs

n-log-n or Divide
n log n
linearithmic Use all parts

n2 quadratic Nested loops

n3 Nested loops
cubic Examine all k-tuples
nk
2n exponential All subsets
n! factorial All permutations

58