Scribd
Upload
2K views

Mathematical Analysis NonRecursive Algorithms

This document discusses analyzing the time efficiency of non-recursive algorithms. It provides steps to determine an algorithm's basic operation, the number of times it is executed based on input size, and establishing its order of growth. Examples are given of finding the largest element in a list, checking element uniqueness, matrix multiplication, and finding binary digits of a decimal number. The key steps are identifying the basic operation, counting how many times it is executed based on input size n, and determining the algorithm's order of growth.

Uploaded by

NIKHIL SOLOMON P URK19CS1045
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
2K views

Mathematical Analysis NonRecursive Algorithms

This document discusses analyzing the time efficiency of non-recursive algorithms. It provides steps to determine an algorithm's basic operation, the number of times it is executed based on input size, and establishing its order of growth. Examples are given of finding the largest element in a list, checking element uniqueness, matrix multiplication, and finding binary digits of a decimal number. The key steps are identifying the basic operation, counting how many times it is executed based on input size n, and determining the algorithm's order of growth.

Uploaded by

NIKHIL SOLOMON P URK19CS1045
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 15

Mathematical Analysis of

Non recursive Algorithms


Analysing the Time Efficiency of Non-recursive Algorithms
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.
Basic Operation
• The operation contributing the most to the total running time of an
algorithm.
• It is typically the most time consuming operation in the algorithm’s
innermost loop.
• Examples: Key comparison operation; arithmetic operation (division
being the most time-consuming, followed by multiplication)
Finding the value of the largest element in a
list of n numbers.

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.
Finding the value of the largest element in
a list of n numbers.
Number of Comparisons
Element uniqueness problem
check whether all the elements in a given array of n elements are
distinct.
Element uniqueness problem
Matrix Multiplication
Given two n × n matrices A and B, find the time efficiency of the definition-
based algorithm for computing their product C = AB. By definition, C is an n ×
n matrix whose elements are computed as the scalar (dot) products of the
rows of matrix A and the columns of matrix B
Matrix Multiplication
Finding the number of binary digits in the
binary representation of a positive decimal integer

The most frequently executed operation here is not inside the while
loop but rather the comparison n > 1 that determines whether the
loop’s body will be executed.
Since the value of n is about halved on each repetition of the loop, the
answer should be about log2 n.
Analysis
At Iteration 1, Length of array = n
At Iteration 2, Length of array = n⁄2
At Iteration 3, Length of array = (n⁄2)⁄2 = n⁄2^2
Therefore, after Iteration k, Length of array = n⁄2^k
After k divisions, the length of array becomes 1
Length of array = n⁄2^k = 1 => n = 2^k
To find the value of k, take base2 log on both sides
=> log2 (n) = log2 (2^k)
=> log2 (n) = k log2 (2)
=> k = log2 (n)
Practice
Practice
Practice

You might also like