Data Structures & Algorithms

Anum Tariq, Lecturer

Department of Software Engineering
Mirpur University of Science and Technology (MUST)
Analysis of Algorithms
• Why need algorithm analysis ?
▫ writing a working program is not good enough
▫ The program may be inefficient!
▫ If the program is run on a large data set, then the
running time becomes an issue
Example: Selection Problem
• Given a list of N numbers, determine the kth largest,
where k  N.
• Algorithm 1:
(1)   Read N numbers into an array
(2)   Sort the array in decreasing order by some simple
algorithm
(3)   Return the element in position k
Example: Selection Problem…
• Algorithm 2:
(1)   Read the first k elements into an array and sort them
in decreasing order
(2)   Each remaining element is read one by one
 If smaller than the kth element, then it is ignored
 Otherwise, it is placed in its correct spot in the array,
bumping one element out of the array.
(3)   The element in the kth position is returned as the
answer.
Example: Selection Problem…
• Which algorithm is better when
▫ N =100 and k = 100?
▫ N =100 and k = 1?
• What happens when N = 1,000,000 and k = 500,000?
• There exist better algorithms
Algorithm Analysis
• We only analyze correct algorithms
• An algorithm is correct
▫ If, for every input instance, it halts with the correct output
• Incorrect algorithms
▫ Might not halt at all on some input instances
▫ Might halt with other than the desired answer
• Analyzing an algorithm
▫ Predicting the resources that the algorithm requires
▫ Resources include
 Memory
 Communication bandwidth
 Computational time (usually most important)
Algorithm Analysis…
• Factors affecting the running time
▫ Computer
▫ Compiler
▫ Algorithm used
▫ Input to the algorithm
 The content of the input affects the running time. typically, the input size
(number of items in the input) is the main consideration
 E.g. sorting problem  the number of items to be sorted
 E.g. multiply two matrices together  the total number of elements in
the two matrices
• Machine model assumed
▫ Instructions are executed one after another, with no concurrent
operations  Not parallel computers
• Advantages of algorithm analysis
▫ To eliminate bad algorithms early
▫ Pinpoints the bottlenecks, which are worth coding
carefully
Worst- / average- / best-case
• Worst-case running time of an algorithm
▫ The longest running time for any input of size n
▫ An upper bound on the running time for any input
▫ Example: Sort a set of numbers in increasing order; and the data
is in decreasing order
▫ The worst case can occur fairly often
 E.g. in searching a database for a particular piece of information
• Best-case running time
▫ sort a set of numbers in increasing order; and the data is already
in increasing order
• Average-case running time
▫ May be difficult to define what “average” means
Running-time of algorithms

• Bounds are for the algorithms, rather than programs

▫ programs are just implementations of an algorithm, and
almost always the details of the program do not affect the
bounds

• Bounds are for algorithms, rather than problems

▫ A problem can be solved with several algorithms, some are
more efficient than others
Asymptotic notation
• Asymptotic Notation is used to describe the running time of an
algorithm - how much time an algorithm takes with a given input,
n.
• There are three different notations: big O, big Theta (Θ), and big
Omega (Ω).
▫ We use O-notation or Big O-notation to give an upper bound on a
function, to within a constant factor. Therefore, it gives the worst-case
complexity of an algorithm.
 E.g. g(n) or cg(n). But we just consider Og(n)..
 F(N) = O(g(N))
▫ Big-Omega notation provides an asymptotic lower bound. Thus, it
provides the best case complexity of an algorithm.
 f(N) = (g(N))
▫ Big-Theta
 Big-Theta means the bound is the tightest possible. Since it represents the
upper and the lower bound of the running time of an algorithm, it is used
for analyzing the average-case complexity of an algorithm.
 f(N) = (g(N))
Big-Oh
• In typical usage, the formal definition of O notation is not used
directly; rather, the O notation for a function f(x) is derived by the
following simplification rules:

▫ If f(x) is a sum of several terms, the one with the largest growth rate is
kept, and all others omitted.

▫ If f(x) is a product of several factors, any constants (terms in the

product that do not depend on x) are omitted.

Briefly saying, when considering the growth rate of a function

using Big-Oh Ignore the lower order terms and the coefficients
of the highest-order term
Big-Oh: example
• For example, let f(x) = 6x4 − 2x3 + 5,5 and suppose we
wish to simplify this function, using O notation, to
describe its growth rate as x approaches infinity. This
function is the sum of three terms: 6x4, −2x3, and 5. Of
these three terms,
▫ The one with the highest growth rate is the one with
the largest exponent as a function of x, namely 6x4.
▫ Now one may apply the second rule: 6x4 is a product
of 6 and x4 in which the first factor does not depend
on x. Omitting this factor results in the simplified form
x4.
▫ Thus, we say that f(x) is a big-oh of (x4) or
mathematically we can write f(x) = O(x4).
General Rules
• For loops
▫ at most the running time of the statements inside the for-loop
(including tests) times the number of iterations.
• Nested for loops

▫ the running time of the statement multiplied by the product of

the sizes of all the for-loops.
▫ it is equal to the number of times the innermost statement
is executed. 
▫ O(N2)
General rules (cont’d)
• Consecutive statements

▫ These just add

▫ O(N) + O(N2) = O(N2)
General rules (cont’d)
• If S1
Else S2
▫ never more than the running time of the test plus the larger of the running
times of S1 and S2.

Here, either sequence 1 will execute, or sequence 2 will execute.

Therefore, the worst-case time is the slowest of the two possibilities:
max(time(sequence 1), time(sequence 2)).
For example, if sequence 1 is O(N) and sequence 2 is O(1) the worst-case
time for the whole if-then-else statement would be O(N).
Example
N
• Calculate  i 3

i 1

1
2
3
4
 Example
N
• Calculate
 i
i 1
3

1 1

2 2N+2

3 4N

4 1

• Lines 1 and 4 count for one unit each

• Line 3: executed N times, each time four units
• Line 2: (1 for initialization, N+1 for all the tests, N for all
the increments) total 2N + 2
• total cost: 6N + 4  O(N)
 19

How to measure complexities?

• Constant: If the algorithm runs for the same
amount of time every time irrespective of the
input size. It is said to exhibit constant time
complexity.
• Linear: If the algorithm runtime is linearly
proportional to the input size then the algorithm is
said to exhibit linear time complexity.
• Exponential: If the algorithm runtime depends on
the input value raised to an exponent then it is
said to exhibit exponential time complexity.
• Logarithmic: When the algorithm runtime
increases very slowly compared to an increase in
input size i.e. logarithm of input size then the
algorithm is said to exhibit logarithmic time
complexity.
20
 21

Log
• The time Complexity of a loop is considered as
O(Log n) if the loop variables are divided/multiplied
by a constant amount. 
• And also for recursive calls in the recursive function,
the Time Complexity is considered as O(Log n).
 22

Example
for (int i = 1; i <= n; i *= c) {
    // some O(1) expressions
} • O(log n)
for (int i = n; i > 0; i /= c) {
    // some O(1) expressions
}

// Here c is a constant greater than 1

for (int i = 2; i <= n; i = pow(i, c)) {
    // some O(1)
}
expressions
• O(log (log n))
// Here fun is sqrt or cuberoot or any other
constant root
for (int i = n; i > 1; i = fun(i)) {
    // some O(1) expressions
}
 23

Binary Search Algorithm: Complexity Analysis

• When dividing an array of length n in two, the total

number of divisions before reaching a one element
array is log2(n) .

• Best Case – 1 comparison

• Worst Case – log2N comparisons

Anum Tariq, Data Structures & Algorithms

 24

Comparing N and log2N Performance

Anum Tariq, Data Structures & Algorithms

 25

Comparison: Discussion
Parameters Bubble Sort Selection Insertion
Sort Sort
Comparison same same Less
comparison
Swaps  swaps swaps n times
almost n*(n-1) at most
Best case O(n) O(n2) O(n)
Complexity
Worst Case O(n2) O(n2) O(n2)

Anum Tariq, Data Structures & Algorithms

 26

Comparison: Discussion
• Reading Assignment

Why the best case time complexity of selection sort is O(n2)

while it is O(n) for bubble sort & insertion Sort?

Anum Tariq, Data Structures & Algorithms

Algorithm 1: Simple
• Exhaustively tries all possibilities (brute force)

2
3

5
6

7
8

9
• O(N3)