Analysis of

Algorithms
Lecture 1
 Analyzing Algorithms

• Algorithm: a sequence of computational steps that takes some values

as Input and produce some values as output.

Be careful to differentiate between:

• Performance: How much time/memory is used when a program is run.

This depends on the machine, compiler, etc. as well as the code we
write.

• Complexity: How do the resource requirements of a program or

algorithm scale, i.e. what happens as the size of the problem being
solved by the code gets larger.

• Note: Complexity affects performance but not vice-versa.

2
Analyzing Algorithms
How to analyze algorithms? (Algorithm Efficiency)

Analysis of algorithms refers to the task of determining how

much computing time and storage an algorithm requires.

Predict the amount of resources required:

 memory: how much space is needed?
 computational time: how fast the algorithm runs?

Fact: the most concern is about the CPU time, which grows with the
size of the input (number of elements entered)

An efficient algorithm uses minimal resources to perform

its functions. 3
Analyzing Algorithms
Why to analyze algorithms?

-The efficiency of an algorithm needs to be determined to

ensure it can perform without the risk of crashes or severe
delays. If an algorithm is not efficient, it is unlikely to be fit for
its purpose.

-It allows you to make quantitative judgments about the value

of one algorithm over another.

- It allows you to predict whether the software will meet any

efficiency constraints that exist.

- Questions such as how well does an algorithm perform in the

best, worst and average cases.
4
Analyzing Algorithms
Main Ways to Measure Algorithm Efficiency?

1. Space complexity

2. Time complexity

5
Space complexity
Space complexity refers to the amount of memory needed
during the execution of a program compared to the
function input, i.e., the amount of memory on a computer
or device that is required.

The memory type could include registers, cache, RAM,

virtual memory, and secondary memory.

6
Space complexity
When analyzing space complexity, you need to consider
four key factors:
1)The memory required to hold the code for the algorithm
2)The memory required to input the data
3)The memory required to output the data (some
algorithms, such as sorting algorithms, do not need
memory to output data and usually just rearrange the input
data).
4)The memory required for working space while the
algorithm is calculated. This can include local variables
and any stack space that is needed.

7
Space complexity
Mathematically, the space equals the sum of the two
components below:
A variable part that includes structured variables
dependent on the problem the algorithm is trying to solve.

A fixed part that is independent of the problem and

consists of instruction space, the space for constants,
fixed-size structure variables, and simple variables.

Therefore, space complexity S(a) of any algorithm is

calculated as follows:
S(a) = c (the fixed part) + v(i) (the variable part which
depends on an instance characteristic i)

8
Time complexity

Time complexity is the total time required to execute an algorithm

Running time = the number of primitive operations (steps) executed

before termination
• Arithmetic operations (+, -, *), data movement, control,
decision making (if, while), comparison

9
Time complexity Example 1
Sort 106 numbers!
E.g.: sorting n numbers

Friend’s computer = 109 instructions/second

Friend’s algorithm = 2n2 instructions

Your computer = 107 instructions/second

Your algorithm = 50nlgn instructions

Your friend =
2  
10 62
 instructions 2000seconds
109 instructions / second
20 times better!!

You = 50  10 6
lg10 6
instructions
100seconds
7
10 instructions / second

10
Time complexity Example 2
• Alg.: MIN (a[1], …, a[n])
m ← a[1];
for i ← 2 to n
if a[i] < m
then m ← a[i];

• Running time:
• the number of primitive operations (steps) executed before
termination
F(n) =1 [first step] + (n) [for loop] + (n-1) [if condition] +
(n-1) [the assignment in then] = 3n – 1

• Order (rate) of growth:

• The leading term of the formula
• Expresses the asymptotic behavior of the algorithm
11
Computing Time complexity

• Each statement cost 1 unit of time except the iterative and

recursion statements

Iterative Statement Examples:

First: Linear loop: Complexity: f(n)=O(n)

For(i=1;i<=n;i++)
for (i=1;i<n; i++) st1
Statement st2
stn

12
Computing Time complexity contd.

Second: Nested loops Complexity f(n)=O(n2)

For(i=1;i<n;i++)
for(j=1;j<n;j++)
statement

Third: Dependent nested loop Complexity f(n)=O(n2)

For(i=1;i<n;i++)
for(j=1;j<i;j++)
statement

13
Types of Time complexity Analysis

• Worst case(e.g. cards reversely ordered)

• Best case(e.g., cards already ordered)

• Average case(general case)

14
Types of Time complexity
Analysis contd.
• Worst case
Define the input for which algorithm takes a long time or
maximum time. In the worst calculate the upper bound of
an algorithm.

Example: In the linear search when search data is not

present at all then the worst case occurs.

15
Types of Time complexity Analysis
contd.
• Best case
Define the input for which algorithm takes less time or
minimum time. In the best case calculate the lower bound
of an algorithm.

Example: In the linear search when search data is present

at the first location of large data then the best case
occurs.

16
Types of Time complexity Analysis
contd.
• Average case
• In the average case take all random inputs and calculate
the computation time for all inputs. Then we divide it by
the total number of inputs.

Average case = all random case time / total no of case

17
Typical Running Time Functions

• 1 (constant running time):

• Instructions are executed once or a few times

• logN (logarithmic)
• A big problem is solved by cutting the original problem in smaller sizes, by a
constant fraction at each step
• N (linear)
• A small amount of processing is done on each input element

• N logN
• A problem is solved by dividing it into smaller problems, solving them
independently and combining the solution

18
Typical Running Time Functions

• N2 (quadratic)
• Typical for algorithms that process all pairs of data items (double nested
loops)

• N3 (cubic)
• Processing of triples of data (triple nested loops)

• NK (polynomial)
• 2N (exponential)
• Few exponential algorithms are appropriate for practical use

19