Analyzing Algorithm:
Complexity
Raja Damanik, M.Sc.
Faculty of Computer Science, University of Indonesia
Design & Analysis of Algorithms 2019
Analyzing the complexity
Analyzing the complexity of an algorithm means predicting
the resources that the algorithm requires.
Resources can mean:
Running time
Memory used
Communication bandwith
etc.
To analyze this, we do counting.
Analyzing the complexity
Sometimes, we care more about a resource than the others.
We should carefully see what resource is limited or what
kind of operation really matters and we should care about.
Most of the time, time complexity is what we care about.
Other complexity can be analyzed using similar strategy (e.g.
counting).
Time Complexity
• The running time of an algorithm depends on the number and type of
operations that are executed.
• Some examples:
• Operations on integer data
• Operations on floating point data
• Accessing an element of an array
• Function calls
• Branching
• Sometimes, a certain type of operations impacts the running time more
severely than others.
• A good analysis will give you a good prediction. A bad one will fool you.
• Having a good analysis needs a good understanding of the environment
where your algorithm runs, e.g. model of your machine, operations you
care about, etc.
RAM model
In this lecture, we will use a standard model in which algorithm in
computer science is analyzed.
We will use generic one-processor RAM (random access machine)
model of computation and implement our algorithm as computer
programs on that machine.
RAM model
RAM model: contains instructions commonly found in real
computers.
Arithmetic (add, subtract, multiply, divide, remainder, floor, and
ceiling)
Data movement (load, store, copy)
Control (conditional and unconditional branch, subroutine call and
return)
Each such instruction is assumed to take a constant amount
of time.
Supports data type: integer, floating point.
Running Time
INSERTION SORT
The running time of insertion sort is
Kinds of algorithm analysis
Assymptotic Notation
The assymptotic notation (such as 𝑂, Ω, Θ) can be used to
simplify the expression that
Is the following statement is correct or not? Discuss with
your neighbor.
The running time of insertion sort is Ω 𝑛2 .
The running time of insertion sort is 𝑂 𝑛2 .
The running time of insertion sort is Θ 𝑛2 .
The worst-case running time of insertion sort is Θ 𝑛2 .
The worst-case running time of insertion sort is 𝑂 𝑛2 .
The best-case running time of insertion sort is Θ 𝑛 .
The best-case running time of insertion sort is 𝑂 𝑛 .
Running time of recursive algorithm
Pseudocode of merge sort
Merge procedure
Exercise
Find the loop invariant of the code fragment 6-
12 from lines 6 to 12 and prove its correctness.
Solving recurrences
• Once we can describe the recurrence for the running time
of an algorithm, we can use the technique from Solving
Recurrences to find the assymptotic tight bound to solution.
• The merge-sort algorithm has running time 𝑇 𝑛 = Θ 𝑛 lg 𝑛 .
