W-2 - L-1 - Asymptotic Notation Complexity Analysis

Asymptotic Notation
Complexity Analysis
Week-02, Lecture-01
Course Code: CSE221 Course Teacher: Tanzina Afroz Rimi

Course Title: Algorithms Designation: Lecturer
Program: B.Sc. in CSE Email: tanzinaafroz.cse@diu.edu.bd
ALGORITHM DEFINITION
A finite set of statements that guarantees an optimal

solution in finite interval of time
GOOD ALGORITHMS?
Run in less time
Consume less memory
But computational resources (time complexity) is usually

more important
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 ?
FACTORS
Hardware
Operating System
Compiler
Size of input
Nature of Input
Algorithm
Which should be improved?

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.
Running time is measured in terms of number of

steps/primitive operations performed
Independent from machine, OS

FINDING RUNNING TIME OF AN
ALGORITHM / ANALYZING 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
SIMPLE EXAMPLE (1)
// 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?

SIMPLE EXAMPLE (2)
// 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
6 7
return s;
} 1,2,8: Once
8
3,4,5,6,7: Once per each iteration
of for loop, N iteration
Total: 5N + 3
The complexity function of the 9
algorithm is : f(N) = 5N +3
SIMPLE EXAMPLE (3) 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”
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
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
COMPARING FUNCTIONS:
ASYMPTOTIC NOTATION
Big Oh Notation: Upper bound
Omega Notation: Lower bound
Theta Notation: Tighter bound

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 N such that for N > N ,
f(N) ≤ c * g(N)
for all sufficiently large N.
BIG OH NOTATION [2]
O(F(N))
16
EXAMPLE (2): COMPARING
FUNCTIONS
4000
 Which function is better?
10 n2 Vs n3 3500
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
17
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(N 2)
Time (steps)
3N = O(N)
Input (size)
N = 60
18
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(n2 log n)
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 n 0such that 0<=f(n)>=cΩ (n) for all n>=n 0
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))
21
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).
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.
PERFORMANCE CLASSIFICATION
f(n) Classification
1 Constant: run time is fixed, and does not depend upon n. Most instructions are executed once, or
only a few times, regardless of the amount of information being processed
log n Logarithmic: when n increases, so does run time, but much slower. Common in programs which
solve large problems by transforming them into smaller problems.
n Linear: run time varies directly with n. Typically, a small amount of processing is done on each
element.
n log n When n doubles, run time slightly more than doubles. Common in programs which break a problem
down into smaller sub-problems, solves them independently, then combines solutions
n2 Quadratic: when n doubles, runtime increases fourfold. Practical only for small problems; typically
the program processes all pairs of input (e.g. in a double nested loop).
n3 Cubic: when n doubles, runtime increases eightfold
2n Exponential: when n doubles, run time squares. This is often the result of a natural, “brute force”
solution.
24
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 ~10 9
64 6 320 384 4096 ~10 19
128 7 640 896 16384 ~10 38
256 8 1280 2048 65536 ~10 76
25
COMPLEXITY CLASSES
) s p e st ( e m i T
26
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

Textbooks & Web References
• Text Book (Chapter 3)
• Reference book ii (Chapter 2)
Thank you
&
Any question?

W-2 - L-1 - Asymptotic Notation Complexity Analysis

Uploaded by

Copyright:

Available Formats

W-2 - L-1 - Asymptotic Notation Complexity Analysis

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

W-2 - L-1 - Asymptotic Notation Complexity Analysis

Uploaded by

Copyright:

Available Formats

Asymptotic Notation

Course Code: CSE221 Course Teacher: Tanzina Afroz Rimi

A finite set of statements that guarantees an optimal

Run in less time

Consume less memory

But computational resources (time complexity) is usually

It would seem that the most obvious way to measure the

Which should be improved?

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

Running time is measured in terms of number of

Independent from machine, OS

Steps means elementary operation like

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

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

int Sum(int A[], int N)

How should we analyse this?

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

int Sum(int A[], int N){

As N grows, the number of steps grow in linear proportion to N for

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

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

Asymptotic Complexity: As N gets large, concentrate on the

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

This gives us an approximation of the complexity of the

Ignores lots of (machine dependent) details, concentrate

Omega Notation: Lower bound

Theta Notation: Tighter bound

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

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

As inputs get larger, any algorithm of a smaller order

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

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

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

If f(n) = O(g(n)) and f(n) ≠ Ω(g(n)), then we say that f(n) is

If f(n) = Ω(g(n)) and f(n) ≠ O(g(n)), then we say that f(n) is

As computer scientist we generally like to express our

If we know the worse case then we can aim to improve it

n3 Cubic: when n doubles, runtime increases eightfold

What happens if we double the input size N?

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

You might also like