COMPLEXITY ANALYSIS

Data Structure and Algorithm in Java

Objectives
2

 Computational and Asymptotic Complexity

 Big-O Notation
 Properties of Big-O Notation
 Ω and Θ Notations
 Examples of Complexities
 Finding Asymptotic Complexity: Examples
 Amortized Complexity
 The Best, Average, and Worst Cases
 NP-Completeness

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Algorithms Definition
3

An algorithm is a procedure or formula for solving a

problem. The word derives from the name of the
mathematician, Mohammed ibn-Musa al-Khwarizmi,
(Baghdad, lived 780 – 850). Al-Khwarizmi's work is the
source for the word algebra as well.
A computer program can be viewed as an elaborate
algorithm. In mathematics and computer science, an
algorithm usually means a small procedure that solves a
recurrent (hồI qui) problem.

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Algorithm Properties
4

 Have Input and Output

 Precision: Clear description
 Finiteness: Terminate with limit steps and result
 Uniqueness
 Generality

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Representations of Algorithms
5

 Algorithms can be represented using:

 Nature language
 Alias programming language
 Diagrams

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Representations of Algorithms
6
Examples – nature language
 find max(a,b,c)
1. Assign x = a
2. If b great than x then assign x=b
3. If c great than x then assign x=c;
4. Result: x => max(a,b,c)

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Representations of Algorithms
7
Examples - alias programming language
Algorithm Max(a,b,c)
Input: int a, b, c
Output: Max(a,b,c)
1. x = a;
2. if b > x then x = b;
3. if c > x then x = c;
4. return x;

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Representations of Algorithms
8
Examples - Diagram

begin x := a

True
b>x x := b

False

c>x
True True

end x := c

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Complexity analysis
9
Need of algorithm analysis
 A problem can be solved by various algorithms
with different efficiencies.
 Example:
 Problem of sorting n of integer number. Suppose:
Executing on the same computer, time per one
operation is 1/1000000 s

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Complexity analysis
10

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Complexity analysis
11 Calculate the execution time of a program in Java
import java.util.Calendar;
public class GioHeThong {
public static void main(String[] args) {
long beginTimes =
Calendar.getInstance().getTimeInMillis();

long a;
long n = 10000;
for (long i=0; i<n;++i)
for(long j =0; j<n; ++j)
a = 1000;

long endTimes =
Calendar.getInstance().getTimeInMillis();
System.out.println("The times in ms for run the
program are:");
System.out.println(endTimes - beginTimes);
}
}

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Complexity analysis
12
Categories of analysis of algorithm
 Precision:
 Proved by mathematics
 Implementation and test
 Simple and public
 Effective:
 Run time
 Space (in memory)

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Complexity analysis
13

 Run time duration of a program depend on

 Size of data input
 Computing system (platform: operation system, speed
of CPU, type of statement…)
 Programming languages
 State of data
 => It is necessary to evaluate the run time of a
program such that it does not depend on computing
system and programming languages.
________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Computational and
14
Asymptotic Complexity
 Computational complexity measures the degree
of difficulty of an algorithm
 Indicates how much effort is needed to apply an
algorithm or how costly it is
 To evaluate an algorithm’s efficiency, use logical
units that express a relationship such as:
 The size n of a file or an array
 The amount of time t required to process
the data
________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Computational and
Asymptotic Complexity (continued)
15

 A measure of efficiency is called asymptotic

complexity
 It is used when disregarding certain terms of a
function
 To express the efficiency of an algorithm
 When calculating a function is difficult or impossible
and only approximations can be
found
f (n) = n2 + 100n + log10n + 1,000

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Computational and
Asymptotic Complexity (continued)
16

Figure 2-1 The growth rate of all terms of function f (n) = n2 + 100n +
log10n + 1,000
________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Big-O Notation
17

 Introduced in 1894, the big-O notation specifies

asymptotic complexity, which estimates the rate of
function growth
 Definition 1: f (n) is O(g(n)) if there exist positive
numbers c and N such that f (n) ≤ cg(n) for all n ≥
N. f(n) is O(g(n)) is read as: f(n) is big-O
of g(n)

Figure 2-2 Different values of c and N for function f (n) = 2n2 + 3n + 1 = O(n2)
calculated according to the definition of big-O
________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Big-O Notation (continued)
18

Figure 2-3 Comparison of functions for different values of c and N

from Figure 2-2
f(n) is O(g(n)) means: f(n) has the upper bound g(n)
________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Properties of Big-O Notation
19

 Fact 1 (transitivity)
If f (n) is O(g(n)) and g(n) is O(h(n)), then f(n) is
O(h(n))
 Fact 2
If f (n) is O(h(n)) and g(n) is O(h(n)), then f(n) + g(n)
is O(h(n))
 Fact 3
The function ank is O(nk)

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Properties of Big-O Notation
20

 Fact 4
The function nk is O(nk+j) for any positive j
 Fact 5
If f(n) = cg(n), then f(n) is O(g(n))
 Fact 6
The function loga n is O(logb n) for any positive
numbers a and b ≠ 1
 Fact 7
loga n is O(lg n) for any positive a ≠ 1, where lg n
= log2 n
________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Ω and Θ Notations
21

 Big-O notation refers to the upper bounds of

functions
 There is a symmetrical definition for a lower bound
in the definition of big-Ω
 Definition 2: The function f(n) is Ω(g(n)) if there
exist positive numbers c and N such that f(n) ≥
cg(n) for all n ≥ N. f(n) is Ω(g(n)) is read as: f(n)
is big-Ω of g(n).

f(n) is Ω (g(n)) means: f(n) has the lower bound g(n)

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Ω and Θ Notations (continued)
22

 The difference between this definition and the

definition of big-O notation is the direction of the
inequality
 One definition can be turned into the other by
replacing “≥” with “≤”
 There is an interconnection between these two
notations expressed by the equivalence
f (n) is Ω(g(n)) iff g(n) is O(f (n))

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Ω and Θ Notations (continued)
23

 Definition 3: f(n) is Θ(g(n)) if there exist positive

numbers c1, c2, and N such that c1g(n) ≤ f(n) ≤
c2g(n) for all n ≥ N
 When applying any of these notations (big-O,Ω,
and Θ), remember they are approximations that
hide some detail that in many cases may be
considered important

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Examples of Complexities
24

 Algorithms can be classified by their time or space

complexities
 An algorithm is called constant if its execution
time remains the same for any number of elements
 It is called quadratic if its execution time is O(n2)

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Examples of Complexities
25

Figure 2-4 Classes of algorithms and their execution times on a computer

________________________________________________________________________________
executing 1 million operations per second (1 sec
CS103 = 10Structure
- Data
6
μsec =and
103Algorithm
msec) in Java
Examples of Complexities
26

Figure 2-4 Classes of algorithms and their execution times on a computer

________________________________________________________________________________
executing 1 million operations per second (1 sec = 106 μsec = 103 msec)
CS103 - Data Structure and Algorithm in Java
Examples of Complexities
27

Figure 2-5 Typical functions applied in big-O estimates

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Finding Asymptotic Complexity
28

 Asymptotic bounds are used to estimate the

efficiency of algorithms by assessing the amount of
time and memory needed to accomplish the task for
which the algorithms were designed
=> Determine the operator active:
1)for (i = sum = 0; i < n; i++)
sum += a[i];
The operator active: sum += a[i];
=> f(n) = n
=> O(n)
________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Finding Asymptotic Complexity
29

2) for (i = 0; i < n; i++) {

for (j = 1, sum = a[0]; j <= i; j++)
sum += a[j];
System.out.println ("sum for subarray 0 through "+i+"
is" + sum);
n 1
}  i  0  1  2  ...  n  1 
i 0
n ( n 1)
2

The operator active: sum += a[j];

n 1
=> f(n)=  i  0  1  2  ...  n  1 
n ( n 1)
2
i 0

=> O(n2)

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Finding Asymptotic Complexity
30

3) for (i = 4; i < n; i++) {

for (j = i-3, sum = a[i-4]; j <= i; j++)
sum += a[j];
System.out.println ("sum for subarray "+(i - 4)+" through
"+i+" is"+ sum);
}

The operator active: sum += a[j];

=> f(n)= (n-3)*(i-(i-3))= (n-3)*4

=> O(n)

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Finding Asymptotic Complexity
31

4) for (i = 0, length = 1; i < n-1; i++) {

for (i1 = i2 = k = i; k < n-1 && a[k] < a[k+1];
k++, i2++);
if (length < i2 - i1 + 1)
length = i2 - i1 + 1;
System.out.println ("the length of the longest
ordered subarray is" + length);
}

The operator active: k < n-1;

Outer loop: (n-1) times
If all numbers are in decreasing order:
Inner loop: one time => f(n)= (n-1)*1 => O(n)
If all numbers are in increasing order:
Inner loop: (n-1-i) times with (i=1->n-2)
=> O(n2)

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Finding Asymptotic Complexity
32

5) int binarySearch(int[] arr, int key) {

int lo = 0, mid, hi = arr.length-1;
while (lo <= hi) {
mid = (lo + hi)/2;
if (key < arr[mid])
hi = mid - 1;
else if (arr[mid] < key)
lo = mid + 1;
else return mid; // success
}
return -1; // failure
}
The best case: one time, the worst case: log2(n)

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
The Best, Average, and Worst Cases
33

 The worst case is when an algorithm requires a

maximum number of steps
 The best case is when the number of steps is the
smallest
 The average case falls between these extremes
Cavg = Σip(inputi)steps(inputi)
=> Searching sequentially

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Amortized Complexity
34

 Amortized analysis:
 Analyzes sequences of operations
 Can be used to find the average complexity of a worst
case sequence of operations
 By analyzing sequences of operations rather than
isolated operations, amortized analysis takes into
account interdependence between operations and
their results

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Amortized Complexity (continued)
35

 Worst case:
C(op1, op2, op3, . . .) = Cworst(op1) + Cworst(op2) + Cworst(op3) + . . .

 Average case:
C(op1, op2, op3, . . .) = Cavg(op1) + Cavg(op2) + Cavg(op3) + . . .

 Amortized:
C(op1, op2, op3, . . .) = C(op1) + C(op2) + C(op3) + . . .

Where C can be worst, average, or best case complexity

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
NP-Completeness
36

 A deterministic algorithm is a uniquely defined

(determined) sequence of steps for a particular
input
 There is only one way to determine the next step that
the algorithm can make
 A nondeterministic algorithm is an algorithm that
can use a special operation that makes a guess
when a decision is to be made (binary search)

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
NP-Completeness (continued)
37

 A nondeterministic algorithm is considered

polynomial: its running time in the worst case is
O(nk) for some k
 Problems that can be solved with such algorithms
are called tractable (dễ xử lý) and the algorithms
are considered efficient
 A problem is called NP-complete if it is NP (it can
be solved efficiently by a nondeterministic
polynomial algorithm) and every NP problem can
be polynomialy reduced to this problem
________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Summary
38

 Computational complexity measures the degree of

difficulty of an algorithm.
 This measure of efficiency is called asymptotic
complexity.
 To evaluate an algorithm’s efficiency, use logical
units that express a relationship.
 This measure of efficiency is called asymptotic
complexity.

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Summary (continued)
39

 Introduced in 1894, the big-O notation specifies

asymptotic complexity, which estimates the rate of
function growth.
 An algorithm is called constant if its execution time
remains the same for any number of elements.
 It is called quadratic if its execution time is O(n2).
 Amortized analysis analyzes sequences of
operations.

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
Summary (continued)
40

 A deterministic algorithm is a uniquely defined

(determined) sequence of steps for a particular
input.
 A nondeterministic algorithm is an algorithm that
can use a special operation that makes a guess
when a decision is to be made.
 A nondeterministic algorithm is considered
polynomial.

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java
References and Readings
41

 Adam Drozdek, 2008, Data Structures and

Algorithms in Java, 3rd edition, Chapter 2
 Kenneth H. Rosen, 2007, Toán rời rạc Ứng
dụng trong Tin học, NXB Giáo dục, Chapter 2

________________________________________________________________________________
CS103 - Data Structure and Algorithm in Java