Fundamentals of the analysis of Algorithm Efficiency

https://www.youtube.com/watch?v=fw_pBjC74Tc
L5: Asymptotic Notations and Basic Efficiency Classes

• The efficiency of an algorithm depends on the amount of time, storage and other resources required
to execute the algorithm. The efficiency is measured with the help of asymptotic notations.
• An algorithm may not have the same performance for different types of inputs. With the increase in
the input size, the performance will change.
• The study of change in performance of the algorithm with the change in the order of the input
size is defined as asymptotic analysis.
• The efficiency analysis framework concentrates on the order of growth of an algorithm’s basic
operation count as the principal indicator of the algorithm’s efficiency.
• To compare and rank such orders of growth, computer scientists use three notations: O (big
oh), (big omega), and (big theta).
O-notation
DEFINITION : A function t (n) is said to
be in O(g(n)), denoted t (n) ∈ O(g(n)),
if t (n) is bounded above by some
constant multiple of g(n) for all large
n, i.e., if there exist some positive
constant c and some nonnegative
integer n0 such that
t (n) ≤ cg(n) for all n ≥ n0.
FIGURE 1. Big-oh notation: t (n) ∈ O(g(n)).
Ω -notation
DEFINITION : A function t (n) is said to
be in Ω(g(n)), denoted t (n) ∈ Ω(g(n)),
if t (n) is bounded below by some
positive constant multiple of g(n) for
all large n, i.e., if there exist some
positive constant c and some
nonnegative integer n0 such that
t (n) ≥ cg(n) for all n ≥ n0.
FIGURE 2. Big-omega notation: t (n) ∈ Ω(g(n)).
θ -notation
DEFINITION : A function t (n) is said to
be in θ(g(n)), denoted t (n) ∈
θ(g(n)), if t (n) is bounded both above
and below by some positive constant
multiples of g(n) for all large n, i.e., if
there exist some positive constants c1
and c2 and some nonnegative integer
n0 such that
c2g(n) ≤ t (n) ≤ c1g(n) for all n ≥ n0. FIGURE 3. Big-theta notation: t (n) ∈ (g(n)).
𝟐. 2𝑛^3−7𝑛+1=Θ(𝑛^3)
Examples:
1. and 2.
Useful Property Involving the Asymptotic
Notations
• Using the formal definitions of the asymptotic notations, we can prove their general properties. The following property, in particular, is useful in
analyzing algorithms that comprise two consecutively executed parts (Ex: Binary search has two parts like sorting and searching.

We can say that,

2g1+3g2 ≤ 3g1+3g2
≤ 3(g1+g2)

Therefore,
c1g1(n)+c2g2(n) ≤ c3g1(n)+c3g2(n)
≤ c3(g1(n)+g2(n))
Using Limits for Comparing Orders of Growth

• Though the formal definitions of big oh, big omega , and theta are indispensable for proving their
abstract properties, they are rarely used for comparing the orders of growth of two specific
functions.
• A much more convenient method for doing so is based on computing the limit of the ratio of two
functions in question. Three principal cases may arise:

• Note that the first two cases mean that t (n) ∈ O(g(n)), the last two mean that t (n) ∈Ω (g(n)),
and the second case means that t (n) ∈ θ (g(n)).
• The limit-based approach is often more convenient than the one
based on the definitions because it can take advantage of the
powerful calculus techniques developed for computing limits, such as,

 L’Hopital’s rule:

 Stirling’s formula:
Examples:
GoalWe aim to compare 𝑛!n! and 2𝑛2 n as 𝑛→∞n→∞, using Stirling's Approximation and limits
to determine their relative growth.

Stirling's formula for factorial is:

n!∼√2πn*(n/e)^n.This approximation simplifies calculations for n!.
Since the ratio 𝑛!/2𝑛→∞, it implies that 𝑛!grows faster than 2^𝑛 .

𝑛!∈Ω(2^𝑛) However, this result also shows that 𝑛! and 2^𝑛2 do not have the same
Symbolically:

order of growth, as their ratio diverges to infinity.

Basic Efficiency Classes: In the below table top to bottom classes are in increasing order of their orders of growth
L6: Mathematical Analysis of Non-recursive & Recursive Algorithms

Mathematical Analysis of Non-recursive Algorithms

EXAMPLE 1 : Consider the problem of finding the value of the largest element in a list of n numbers. For
simplicity, we assume that the list is implemented as an array. The following is pseudocode of a standard
algorithm for solving the problem.

A[5]=21,31,45,25,12
General Plan for Analyzing the Time Efficiency
1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm’s basic operation. (As a rule, it is located in the
innermost loop.)
3. Check whether the number of times the basic operation is executed depends
only on the size of an input. If it also depends on some additional property, the
worst-case, average-case, and, if necessary, best-case efficiencies have to be
investigated separately.
4. Set up a sum expressing the number of times the algorithm’s basic
operation is executed.
5. Using standard formulas and rules of sum manipulation, either find a
closed form formula for the count or, at the very least, establish its order of
growth.

L1.27
• The array size in the algorithm is n and the operations that are going to be executed most often are in the
algorithm’s for loop. There are two operations in the loop’s body:
• The comparison A[i] > maxval
• The assignment maxval ← A[i].
• Which of these two operations should we consider basic?
• Since the comparison is executed on each repetition of the loop and the assignment is not, we should consider
the comparison to be the algorithm’s basic operation.
• Note : The number of comparisons will be the same for all arrays of size n; therefore, in terms of this metric,
there is no need to distinguish among the worst, average, and best cases.
• Let C(n) be the number of times this comparison is executed. The algorithm makes one comparison on each
execution of the loop, which is repeated for each value of the loop’s variable i within the bounds 1 and n − 1,
inclusive. Therefore, we get the following sum for C(n):

is a special case of formula for lower limit (l) =

1 and upper limit (u) = n − 1,……will see in
next slide.

• This is an easy sum to compute because it is nothing other than 1 repeated n − 1 times.

L1.28
L1.29
EXAMPLE 2: Element uniqueness problem
0 1 2 3 4 n-2 n-1

5 8 9 7 10 3 2

Best Case situation: If the two first elements of the array are the same, then we can exit after one comparison.
Best case = 1 comparison.

Worst-case situation:The basic operation is the comparison in the inner loop. The worst-case happens for two-
kinds of inputs:
- Arrays with no equal elements
- Arrays in which only the last two elements are the pair of equal elements.

L1.30
L1.31
Example 3: Matric Multiplication

L1.32
No j & I terms in the summation, so
take n out & 1 will remain

L1.33
Mathematical Analysis of Recursive Algorithms
General Plan for Analyzing the Time Efficiency
1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm’s basic operation.
3. Check whether the number of times the basic operation is executed can
vary on different inputs of the same size; if it can, the worst-case, average-
case, and best-case efficiencies must be investigated separately.
4. Set up a recurrence relation, with an appropriate initial condition, for the
number of times the basic operation is executed.
5. Solve the recurrence or, at least, as certain the order of growth of its
solution.

L1.35
• The basic operation of the algorithm is multiplication, whose number of executions we denote M(n).
Since the function F (n) is computed according to the formula
F (n) = F (n − 1) . n for n > 0,
the number of multiplications M(n) needed to compute it must satisfy the equality

• Indeed, M(n − 1) multiplications are spent to compute F (n − 1), and one more multiplication is needed to
multiply the result by n.
• Our goal now is to solve the recurrence relation M(n) = M(n − 1) + 1, i.e., to find an explicit formula for
M(n) in terms of n only.
• From the several techniques available for solving recurrence relations, we use what can be called the
method of backward substitutions. The method’s idea (and the reason for the name) is immediately clear
from the way it applies to solving our particular recurrence:

L1.36
• After inspecting the first three lines, we see an emerging pattern, which makes it
possible to predict not only the next line (what would it be?) but also a general
formula for the pattern:

M(n) = M(n − i) + i.

• What remains to be done is to take advantage of the initial condition given. Since
it is specified for n = 0, we have to substitute i = n in the pattern’s formula to get
the ultimate result of our backward substitutions:

M(n) = M(n − 1) + 1 = ... = M(n − i) + i = ... = M(n − n) + n = n.

• Overall time Complexity: O(n)

L1.37
Example 2: Tower of Hanoi puzzle

L1.38
L1.39
L1.40
Example 3: The number of binary digits in n’s binary representation

L1.41
Exercise:

1. Write a note on Performance comparison between Recursive Algorithms and Non-

Recursive Algorithms

Refer below links for more practice on Recursive Algorithms and Non-Recursive Algorithms

2. https://www.geeksforgeeks.org/practice-set-recurrence-relations/?ref=rp
3. https://sites.radford.edu/~nokie/classes/360/recurrence.eqns.revised.html

L1.42