PROGRAM

EFFICIENCY
TIME COMPLEXITY
&
ANALYSIS

COURSE INSTRUCTOR
Prof Dr Arfan Jaffar
ALGORITHM REVIEW

 An algorithm is a definite procedure for solving a problem in

finite number of steps
 Algorithm is a well defined computational procedure that
takes some value (s) as
input, and produces some value (s) as output.
 Algorithm is finite number of computational statements that
transform input into the output
GOOD ALGORITHMS ?

 Run in less time

 Consume less memory

But computational resources (time complexity) is usually

more important
MEASURING EFFICIENCY

 The efficiency of an algorithm is a measure

of the amount of resources consumed in
solving a problem of size n.
 The resource we are most interested in is
time
 We can use the same techniques to
analyze the consumption of other
resources, such as memory space.
 It would seem that the most obvious way
to measure the efficiency of an
algorithm is to run it and measure how
much processor time is needed
 WHAT IS ASYMPTOTIC NOTATION?
Asymptotic notations are mathematical tools that help us describe
how the running
time of an algorithm grows as the input size (n) becomes very
large.
Why do we need it?
 To compare Complexities of different algorithms.
 To know how efficient an algorithm will be when data grows really
big.
 To ignore unnecessary details (like +5 or ×2) and just keep the
dominant part.
Example:
Algorithm A takes 2n + 5 steps.
Algorithm B takes n² + 3n + 10 steps.
👉 When n is huge:
2n + 5 behaves like n
ASYMPTOTIC CASES

When we talk about asymptotic notations,

We often analyze algorithms in different cases depending on the
type of inputs the algorithm gets.
There are three different cases
1. Best Case
2. Average Case
3. Worst Case.
BEST CASE

Definition: The time taken by the algorithm when the

input is the most favorable (the easiest case).
Meaning: Minimum time the algorithm will take.
Example: For linear search, if the target element is the
first element in the array, that’s the best case.

Notation Used: Ω (Omega).

AVERAGE CASE

Definition: The time taken by the algorithm on

average inputs, i.e., considering all possible inputs
and averaging the performance.
Meaning: Expected/typical running time.
Example: For linear search, if the element is
randomly located somewhere in the array, on
average you will search half the array.
Notation Used: Θ (Theta).
WORST CASE

Definition: The time taken by the algorithm when the

input is the least favorable (the hardest case).
Meaning: Maximum time the algorithm can take.
Example: For linear search, if the target element is the
last element or not even present, that’s the worst case.
Notation Used: O (Big O).
 CASE TO FOCUS FOR DESIGN ALGO
When designing an algorithm, we focus mostly on the
Worst Case (Big O), because it guarantees performance in
the most
Why do we difficult situations.
focus on Worst
Case? Reliability:
 The worst case guarantees
the algorithm will never
perform worse than this
bound.
 Example: If you know an algorithm takes at most O(n log n) steps, it will
never take longer than that.
Predictability:
 In real systems, we must ensure the algorithm runs efficiently even in the
hardest situation.
 Imagine an ATM or medical system it must work fast even in the worst
possible scenario.
Security & Robustness:
 Worst-case analysis avoids hidden performance issues that attackers or
 RUNNING TIME OF AN ALGORITHM

 Depends upon
 Input Size
 Nature of Input
 Generally time grows with size of input, so running time of an
algorithm is usually measured as function of input size.
 Running time is measured in terms of number of
steps/primitive operations performed
 Independent from machine, OS
FINDING RUNNING TIME OF AN
ALGORITHM / ANALYZING AN
ALGORITHM
 Running time is measured by number of steps/primitive
operations performed
 Steps means elementary operation like
 ,+, *,<, =, A[i] etc

 We will measure number of steps taken in term of size of

input
EXAMPLE (1) – CONSTANT RUNNING TIME
1
int getFirst(int
a[], int n) {
} return a[0];
2

Counting
operations Array
access = 1 Return
=1
EXAMPLE (2) - CONSTANT RUNNING TIME
#include
<iostream>
using
namespace
int main() { std;
int a = 10, b O(1)
= 20; int sum O(1)
= a + b; cout O(1)
<< sum; O(1)
return 0;
}

Counting
No matter how large inputs are, the program performs
only a few fixed [Link] time does not
operations
Exact count: 𝑇(𝑛)= 1 + 1 + 1 + 1 = 4(constant) => O(c)
depend on input size.
 EXAMPLE (3) - LINEAR RUNNING TIME

#include
<iostream>
using
O(1)
namespace
int n; std; O(1)
intcin
main()
>> {
n;
for(int i = 0; i < n;
O(n)
O(1) i++) { O(n+1)
cout << i
} << " ";
O(n)
return
} 0; O(1)

T(n) = 1 + 1 + 1+ (n+1) + n+ n +1 = 3n+4 =>

O(n) Linear Time
 EXAMPLE (4)- QUADRATIC RUNNING TIME

int O(1)
main() O(1)
{ int
n; i+
O(n+1)
cin >> +) O(n)
O(1) n; for(int j = 0;
O(n(n))
{
j < n;
for(int i j++)
={ 0; i
O(n(n+1))
O(n) < }n; cout << i << "," << j O(n(n))
} << " ";
O(1)
return
} 0;
T(n)= 1 + 1 + 1+ (n+1) + n + n(n+1) +
n(n) + n(n) + 1
= 3n2 + + 3n + 5
 EXAMPLE (5)- LOGARITHMIC TIME
int O(1)
main() O(1)
{ int
n; O(log(n) + 1)
cin >> n;
while(n > // reduces input size by half O(log(n))
1) cout << each
n step O(log(n))
{ } << " ";
n = n / 2;
O(1)
return
} 0;
T(n) = 1 + 1 + (log(n) + 1) + log(n) +
log(n) + 1
= 3 log(n) + 4
= O(log(n))
EXAMPLE (6): N LOG (N) TIME
void exampleNlogN(int
n) { for (int i = 1; i
<= n; i++) {
int j = 1;
while (j <
n) {
j = j * 2;
cout
<< "*";
}
}
 EXAMPLE (6): N LOG (N) TIME
Outer Loop: for (int i = 1; i <=

contributes 𝑂(𝑛).
n; i++) Runs n times →

Inner Loop: while (j < n) { j

𝑗=1.
= j * 2; } Starts with

Each iteration multiplies 𝑗 by

So values of 𝑗: 1, 2, 4, 8, 16 … until
2.

𝑗≥n. How many steps?

2𝑘 ≤ 𝑛
Solve:
where k is number of
iterations Taking log base 2 on both

𝑘 ≤ log2(𝑛)
sides:
 EXAMPLE (6): WHY INNER LOOP IS
LOG(N)
Step ?
1:What happens in
•Inner
At the start
loop?j=1
• After 1st iteration → j = 2
• After 2nd iteration → j = 4
• After 3rd iteration → j = 8
• …and so on.
So j becomes powers of 2:
j = 2k
(where k = number of times the loop
has run).
Step 2:When does loop
stop?
The condition is while (j
< n). It stops when j ≥

But since 𝑗=2𝑘, this

n.

means:
2k ≥ n

𝑘
Step 3: Solve for

To find how many times

 f(n) Classification
1 Constant: run time is fixed, and does not depend upon n. Most instructions are
executed once, or only a few times, regardless of the amount of information
being processed
log n Logarithmic: when n increases, so does run time, but much slower. Common in
programs which solve large problems by transforming them into smaller
problems.

n Linear: run time varies directly with n. Typically, a small amount of processing
is done on each element.
n log n When n doubles, run time slightly more than doubles. Common in programs
which break a problem down into smaller sub-problems, solves them
independently, then combines solutions
n2 Quadratic: when n doubles, runtime increases fourfold. Practical only for small
problems; typically the program processes all pairs of input (e.g. in a double
nested loop).
n3 Cubic: when n doubles, runtime increases eightfold

2n Exponential: when n doubles, run time squares. This is often the result of a natural,
“brute force” solution.
What happens if we double the input size N?

N log2N 5N N log2N N2 2N
8 3 40 24 64 256
16 4 80 64 256 65536
32 5 160 160 1024 ~109
64 6 320 384 4096 ~1019
128 7 640 896 16384 ~1038
256 8 1280 2048 65536 ~1076
STANDARD ANALYSIS TECHNIQUES

 Constant time statements

 Analyzing Loops
 Analyzing Nested Loops
 Analyzing Sequence of
Statements
 Analyzing Conditional
Statements
CONSTANT TIME STATEMENTS
 Simplest case: O(1) time
statements
 Assignment statements of simple
data types

int x = y;
 Arithmetic operations:

x = 5 * y + 4 - z;
 Array referencing:

A[j] = 5;
 Array assignment:

 j, A[j] = 5;
 Most conditional tests:
 ANALYZING LOOPS[1]
 Any loop has two parts:
 How many iterations are
performed?
 How many steps per iteration?

int sum = 0,j;

for (j=0; j < N;
j++) sum =
sum +j;
 Loop executes
N times (0..N-1)
 4 = O(1) steps
per iteration
 Total time is N *
O(1) = O(N*1) =
O(N)
 ANALYZING LOOPS[2]

 What about this for loop?

int sum =0, j;
for (j=0; j <
100; j++) sum
= sum +j;
 Loop executes
100 times
 4 = O(1) steps
per iteration
 Total time is 100 *
O(1) = O(100 * 1)
= O(100) = O(1)
ANALYZING NESTED LOOPS[1]
 Treat just like a single loop and evaluate each level
needed:
of nesting as
int j,k;
for (j=0; j<N; j+
+) for (k=N;
k>0; k--)
sum += k+j;
 Start with outer
loop:
 How many
iterations? N
 How much time
per iteration?
Need to
evaluate inner
loop
ANALYZING NESTED LOOPS[2]

 What if the number of iterations of one loop depends on the

counter of the
other?
int j,k;
for (j=0; j < N;
j++) for (k=0;
k < j; k++)
sum += k+j;
 Analyze inner and
outer loop together:
 Number of
iterations of the
inner loop is:
 0 + 1 + 2 + ... +
ANALYZING SEQUENCE OF STATEMENTS

 For a sequence of statements, compute their complexity

functions individually and add them up
for (j=0; j < N; j++)
O(N2
for (k =0; k < j;
)
k++) sum =
sum + j*k;
for (l=0; l < N; l++) O(N)
sum = sum -l;
cout<<“Sum=”< O(1)
<sum;
Total cost is O(N2) +
O(N) +O(1) = O(N2) SUM RULE