BIL211-Veri Yapıları

Lecture 2: Algorithm Analysis

Assist. Prof. Dr. Duygu SİNANÇ TERZİ

Amasya University
Faculty of Engineering
Department of Computer Engineering
Assignment - 1
Recap C Programming
In-class Test - 1
Write a function that will return the sum of all the
elements of the integer array.

Given: array and its size as an argument.

Answer of In-class Test - 1
Analysis of
Algorithms
Algorithm
● An algorithm can be defined as a
step by step procedure that
provides solution to a given
problem.
● In computing terms, an algorithm
is described a little differently. It
is defined as a hierarchy of steps
used for computational
procedures, which usually starts
with an input value and generates
the desired output.

6
Characteristics of an Algorithm
There are certain key characteristics that an algorithm must possess. These
characteristics are:
● An algorithm must comprise of a finite number of steps.
● It should have zero or more valid and clearly defined input values.
● It should be able to generate at least a single valid output based on a valid
input.
● It must be definite. Each instruction in the algorithm should be defined
clearly.
● There should be no ambiguity regarding the order of execution of algorithm
steps.
● It should be correct. It should be able to perform the desired task of
generating correct output from the given input.
● It should be able to terminate on its own. It should not go into an infinite
loop.
7
Algorithm Development Life Cycle
● In the life cycle of an algorithm for the development of an algorithm, the
following phases are involved:

○ Design Phase
○ Writing Phase
○ Testing Phase
○ Analysing Phase

8
Design Phase
● Given an algorithmic problem, where do you even start?
● Over the last half a century, computer scientists have discovered that
many algorithms share similar ideas, even though they solve very
different problems.
● Before solving a new problem, the general tendency is to look for the
similarity of the current problem to other problems for which we have
solutions (reducing one problem to another).
● In the design phase of an algorithm, one of the algorithmic design
techniques is used.

9
Design Phase
● There are many ways of classifying algorithms and a few of them are
shown below:
● Recursion or Iteration
● Procedural or Declarative (Non-procedural)
● Serial or Parallel or Distributed
● Greedy Method
● Divide and Conquer Method
● Dynamic Programming
● Randomized algorithms
● …

10
Design Phase
● A complex algorithm is often divided into smaller units called modules.
● This process of dividing an algorithm into modules is called
modularization.
● The key advantages of modularization are as follows:
○ It makes the complex algorithm simpler to design and implement.
○ Each module can be designed independently. While designing one
module, the details of other modules can be ignored, thereby
enhancing clarity in design which in turn simplifies
implementation, debugging, testing, documenting, and
maintenance of the overall algorithm.

11
Design Phase
● A top-down design approach starts by dividing the complex algorithm into one
or more modules. These modules can further be decomposed into one or more
sub-modules, and this process of decomposition is iterated until the desired
level of module complexity is achieved.
● A bottom-up approach is just the reverse of top-down approach. In the bottom-
up design, we start with designing the most basic or concrete modules and then
proceed towards designing higher level modules.

12
Writing Phase
● The typical definition of algorithm is «a formally defined procedure for
performing some calculation».
● If a procedure is formally defined, then it can be implemented using a
formal language, and such a language is known as a programming
language.
● A programming language is a system of notation for writing computer
programs.
● Most programming languages are text-based formal languages, but
they may also be graphical.
● The description of a programming language is usually split into the two
components of syntax (form) and semantics (meaning), which are
usually defined by a formal language

13
Writing Phase
An algorithm is written using the following basic methods:
● Sequence means that each step of an algorithm is executed in a specified order.
● Decision statements are used when the execution of a process depends on the
outcome of some condition. A condition in this context is any statement that
may evaluate to either a true value or a false value.
● Repetition involves executing one or more steps for a number of times. These
loops execute one or more steps until some condition is true.

14
Testing Phase
● After writing an algorithm, it is necessary to check whether the
algorithm is correct or not.
● A logic error (or logical error) is a ‘bug’ or mistake in a program’s source
code that results in incorrect or unexpected behaviour. It is a type of
runtime error that may simply produce the wrong output or may cause a
program to crash while running.
● A syntax error is an error in the source code of a program. Since
computer programs must follow strict syntax to compile correctly, any
aspects of the code that do not conform to the syntax of the
programming language will produce a syntax error.
● When any error is found, then go back to the algorithm design phase
and redesign the algorithm.

15
Analysing Phase
● It is not uncommon to have multiple algorithms to tackle the same
problem, but the choice of a particular algorithm must depend on the
complexity of the algorithm.
● Analysing an algorithm means determining the amount of resources
needed to execute it.

16
Analysing Phase
● To compare algorithms, let us define a few objective measures:
○ Execution times? Not a good measure as execution times are
specific to a particular computer.
○ Number of statements executed? Not a good measure , since the
number of statements varies with the programming language as
well as the style of the individual programmer.
○ Running time? Let us assume that we express the running time of
a given algorithm as a function of the input size and compare these
different functions corresponding to running times.

17
Analysing Phase
● Algorithms are generally designed to work with an arbitrary number of
inputs, so the efficiency or complexity of an algorithm is stated in
terms of time and space complexity.
○ The space complexity of an algorithm is the amount of computer
memory that is required during the program execution as a
function of the input size.
○ The time complexity of an algorithm is basically the running time
of a program as a function of the input size.

18
Space Complexity
The space needed by a program depends on the following three factors:
● Instruction space
○ Affected by: the compiler, compiler options, target computer (cpu)
● Data space
○ Affected by: the data size/dynamically allocated memory, static
program variables,
● Run-time stack space
○ Affected by: the compiler, run-time function calls and recursion,
local variables, parameters

19
Time Complexity
The running time depends on many factors:
● The speed of the computer
○ CPU (not just clock speed), I/O, etc.
● The compiler, compiler options .
● The quantity of data
○ ex. search a long list or short.
● The actual data
○ ex. in the sequential search if the name is first or last.

20
Time Complexity
● Worst-case running time: This denotes the behaviour of an algorithm with
respect to the worst possible case of the input instance. The worst-case
running time of an algorithm is an upper bound on the running time for any
input. Therefore, having the knowledge of worst-case running time gives us
an assurance that the algorithm will never go beyond this time limit.
● Average-case running time: It specifies the expected behaviour of the
algorithm when the input is randomly drawn from a given distribution.
Average-case running time assumes that all inputs of a given size are
equally likely.
● Best-case running time: The term ‘best-case performance’ is used to
analyse an algorithm under optimal conditions. However, while developing
and choosing an algorithm to solve a problem, we hardly base our decision
on the best-case performance. It is always recommended to improve the
average performance and the worst-case performance of an algorithm.
21
Time–Space Trade-off
● The best algorithm to solve a particular problem at hand is no doubt the
one that requires less memory space and takes less time to complete
its execution.
● But practically, designing such an ideal algorithm is not a trivial task.
● There can be more than one algorithm to solve a particular problem. One
may require less memory space, while the other may require less CPU
time to execute.
● Hence, there exists a time–space trade-off among algorithms. So, if
space is a big constraint, then one might choose a program that takes
less space at the cost of more CPU time. On the contrary, if time is a
major constraint, then one might choose a program that takes
minimum time to execute at the cost of more space.

22
Expressing Time and Space Complexity
● The time and space complexity can be expressed using a function f(n)
where n is the input size for a given instance of the problem being
solved.
● Expressing the complexity is required when
○ We want to predict the rate of growth of complexity as the input
size of the problem increases.
○ There are multiple algorithms that find a solution to a given
problem and we need to find the algorithm that is most efficient.

23
Expressing Time and Space Complexity
● Input size is the number of elements in the input, and depending on the
problem type, the input may be of different types. The following are the
common types of inputs:
○ Size of an array
○ Polynomial degree
○ Number of elements in a matrix
○ Number of bits in the binary representation of the input
○ Vertices and edges in a graph.

24
Expressing Time and Space Complexity
● If a function is linear (without any loops or recursions), the efficiency of
that algorithm or the running time of that algorithm can be given as the
number of instructions it contains.
● However, if an algorithm contains loops, then the efficiency of that
algorithm may vary depending on the number of loops and the running
time of each loop in the algorithm.

25
Linear Loops
● To calculate the efficiency of an algorithm that has a single loop, we
need to first determine the number of times the statements in the loop
will be executed.
● This is because the number of iterations is directly proportional to the
loop factor.

for(i=0;i<100;i++)
statement block; f(n)

for(i=0;i<100;i+=2)
statement block; f(n/2)

26
Logarithmic Loops
● We have seen that in linear loops, the loop updation statement either
adds or subtracts the loop-controlling variable.
● However, in logarithmic loops, the loop-controlling variable is either
multiplied or divided during each iteration of the loop.
● The logarithm is the inverse of exponentiation. For example;

○ 23 = 8 log 2 8 = 3
○ 104 = 10000 log10 10000 = 4

27
Logarithmic Loops
for(i=1;i<1000;i*=2)
statement block;

f(n)= log n
for(i=1000;i>=1;i/=2)
statement block;

28
Nested Loops
● Loops that contain loops are known as nested loops.
● In order to analyze nested loops, we need to determine the number of
iterations each loop completes.
● The total is then obtained as the product of the number of iterations in
the inner loop and the number of iterations in the outer loop.

29
Nested Loops
Linear logarithmic loop
for(i=0; i<10; i++)
for(j=1; j<10; j*=2) f(n)=[Link](n)
statement block;

Quadratic loop
for(i=0; i<10; i++)
for(j=0; j<10; j++) f(n)=n.n
statement block;

Dependent quadratic loop

for(i=0; i<10; i++)
for(j=0; j<=i; j++) f(n)=n.(n+1)/2
statement block;
30
Commonly Used Rates of Growth

31
Program Effort

32
Asymptotic Notation
● Asymptotic notation is the most simple and easiest way of describing
the running time of an algorithm.
● It represents the efficiency and performance of an algorithm in a
systematic and meaningful manner.
● Asymptotic notations describe time complexity in terms of three
common measures, best case (or ‘fastest possible’), worst case (or
‘slowest possible’), and average case (or ‘average time’).
● The four most important asymptotic notations are:
○ Big O notation
○ Omega notation
○ Theta notation
○ Little o Notation

33
Big-O Notation
● Order of magnitude/asymptotic categorization eliminates hardware
from consideration and expresses efficiency in terms of data size.
● We have seen that the number of statements executed in the program
for n elements of the data is a function of the number of elements,
expressed as f(n).
● This factor is the Big-O, and is expressed as O(n).
● Big O notation provides a strict upper bound for f(n). This means that
the function f(n) can do better but not worse than the specified value.
● Even if the expression derived for a function is complex, a dominant
factor in the expression is sufficient to determine the order of the
magnitude of the result and, hence, the efficiency of the algorithm.
● When expressing complexity using the Big O notation, constant
multipliers are ignored.
34
Finding the Big-O – Example1
Step 1 : Find efficiency of each loop.

35
Finding the Big-O – Example1
Step 2: Combine
Multiply nested, add sequential.

36
Finding the Big-O – Example1
Step 3: Simplify

37
Finding the Big-O – Example2
What is the complexity of the program given below:

38
Finding the Big-O – Example2
What is the complexity of the program given below:

n/2

n/2

log(n)

O(𝑛2 logn)

39
Finding the Big-O – Example3
Consider-
○ There is a linear array ‘a’ of size ‘n’.
○ Linear search algorithm is being used to search an element ‘item’ in
this linear array.
○ It traverses the array sequentially to locate the required element.
○ If search ends in success, it sets loc to the index of the element
otherwise it sets loc to -1.

40
Finding the Big-O – Example3
● In the best possible case, the element being searched may be found at the first
position. Linear search algorithm takes O(1) operations.
● In the worst possible case, the element being searched may be present at the
last position or not present in the array at all. O(n)

41
Finding the Big-O – Example4
Consider-
○ There is a linear array ‘a’ of size ‘n’.
○ Bubble sort algorithm is an in-place sorting algorithm.
○ Bubble sort compares the adjacent elements of the array.
○ It then swaps the two elements if they are in the wrong order.

42
Finding the Big-O – Example4
● In best case, the array is already sorted but still to check, bubble sort performs
O(n) comparisons.
● The worst situation for bubble sort is when the list's smallest element is in the
last position. O(𝑛2 )

43
Algorithm Efficiency
The various functions grow with n: (2𝑛 grows very rapidly with 𝑛)

44
Algorithm Efficiency
The time that a 1,000,000,000 instructions per second computer needs to
execute an algorithm of complexity f(n) instructions:

45
Limitations of Big-O
There are certain limitations with the Big O notation of expressing the
complexity of algorithms. These limitations are as follows:

● Many algorithms are simply too hard to analyze mathematically.

● There may not be sufficient information to calculate the behavior of the
algorithm in the average case.
● Big O analysis only tells us how the algorithm grows with the size of the
problem, not how efficient it is, as it does not consider the programming
effort.
● It ignores important constants. For example, if one algorithm takes O(𝑛2 )
time to execute and the other takes O(100000𝑛2 ) time to execute, then as
per Big O, both algorithm have equal time complexity. In real-time systems,
this may be a serious consideration.

46
Assignment - 2
Find the complexity