Analysis of Algorithms
P Jayakrishnan
Objective
Algorithms in Physical Design
Algorithm complexity
Asymptotic Analysis
Big – O Notation
Algorithms in Physical Design
Physical Design is a complex optimization problem
Minimum chip area
Minimum wire length
Minimum Via
Different Algorithms used for different optimization goals
Trade-off among multiple goals
Algorithm complexity
Time Complexity: Running time of a program as a function of the size of the
input.
Space Complexity: Some forms of analysis could be done based on how
much space an algorithm needs to complete its task.
Worst-case: f (n) defined by the maximum number of steps taken on any
instance of size n.
Best-case: f (n) defined by the minimum number of steps taken on any
instance of size n.
Average case: f (n) defined by the average number of steps taken on any
instance of size n.
Analysis of Algorithm
Performance of Algorithm is important
Consider a messaging application detects the touch of an alphabet takes 1 second
Given two algorithms which one is better
Implement both the algorithms and run the two programs on your computer for
different inputs and see which one takes less time
It might be possible that for some inputs, first algorithm performs better than the
second. And for some inputs second performs better.
It might also be possible that for some inputs, first algorithm perform better on one
machine and the second works better on other machine for some other inputs.
Asymptotic Analysis
Performance of an algorithm is evaluated in terms of input size
Asymptotic Analysis
The word Asymptotic means approaching a value or curve arbitrarily
closely
The asymptotic behavior of a function f(n) refers to the growth
of f(n) as n gets large
Asymptotic notations describe the running time of an algorithm when the
input tends towards a particular value or a limiting value.
Function ƒ (n) = n2+3n, the function "ƒ (n) is said to be asymptotically
equivalent to n2 as n → ∞", and here is written symbolically as ƒ (n) ~ n2
Big ‘O’ Notation
Big-o notation: Big-o is the formal method of expressing the upper bound of
an algorithm's running time. The function f (n) = O (g (n)) if and only if exist
positive constant c and such that
f (n) ⩽ c .g (n)
3n+2=O(n) as 3n+2≤4n for all n≥2
3n+3=O(n) as 3n+3≤4n for all n≥3
Omega (Ω) Notation
The function f (n) = Ω (g (n)) if and only if there exists positive constant c and
n0 such that
f(n) ≥ k * g (n) for all n, n≥ n0
3n+2= Ω(n) as 3n+2 ≥ n
Theta (θ)
The function f (n) = θ (g (n)) if and only if there exists positive constant k1,
k2 and k0 such that
k1 * g (n) ≤ f(n)≤ k2 g(n)for all n, n≥ n0
3n+2= θ(n) as 3n+2 ≥ n
3n+2≥3n and 3n+2≤ 4n, for n
k1=3, k2=4, and n0=2
Time complexity analysis –some
general rules
We analyse the time complexity for
Very large input
Worst case scenario
Ignore lower order terms
Ignore the constant multiplier
Calculation of time complexity -
Examples
f(n) = 2n2 + 3n + 4
f(n) = O(n2)
f(n) = n2logn + n
f(n) = O(n2logn)
f(n) = n!
f(n) = O(nn)
Example 1: Example 2:
for( i=0; i<n; i++) for( i=1; i<n; i=i+2)
{ {
statement; statement;
} }
time complexity = O(n) time complexity = O(n)
Example 3: Example 4:
for( i=0; i<n; i++) for( i=1; i < n; i = i × 2)
{ {
for( j=0; j<n; j++)
statement;
statement;
}
}
time complexity = O(logn)
time complexity = O(n2)
Summary
Algorithms in Physical Design
Algorithm complexity
Asymptotic Analysis
Big – O Notation
