Order of Growth

We expect our algorithms to work faster for all values of N. Some algorithms execute faster for
smaller values of N. But, as the value of N increases, they tend to be very slow. ➢ So, the behavior
of some algorithms changes with increase in value of N. ➢ This change in behavior of the algorithm
and algorithm’s efficiency can be analyzed by considering the highest value of N.

Minimum Element in Array

function findMinElement(array):
if array is empty:
return "Array is empty" 1
1
// Initialize minElement with the first element
of the array
minElement = array[0]
2
// Iterate through the array starting from the
second element
for each element in array from index 1 to
length - 1: n
// Compare current element with
minElement
if element < minElement:
// Update minElement if the current 2(n-1)
element is smaller
minElement = element
// minElement now contains the minimum 2(n-1)
element in the array
return maxElement
1
=5n+1

Maximum Element in Array

function findMaxElement(array):
if array is empty: 1
return "Array is empty" 1

// Initialize maxElement with the first element

of the array
maxElement = array[0] 2

// Iterate through the array starting from the

second element
for each element in array from index 1 to n
length - 1:
// Compare current element with
maxElement
if element > maxElement: 2(n-1)
// Update maxElement if the current
element is bigger
maxElement = element 2(n-1)

// maxElement now contains the maximum

element in the array 1
return maxElement =5n+1

True

False

False

O(n2)

O(n3)
Write psuedo code to count how many elements are even in the given list.
function countEvenElements(list):
// Initialize a variable to store the count of
even elements
evenCount = 0 1

// Iterate through each element in the list

for each element in list: n+1
// Check if the current element is even
if element % 2 == 0: n
// Increment the count if the element is
even
evenCount = evenCount + 1 2(n)

// The variable evenCount now contains the

count of even elements
return evenCount 1
=4n+3

Write a pseudo code for Linear Search – Finding if an element is present in an array.
function linearSearch(array, target):
// Iterate through each element in the array
for index from 0 to length of array - 1: n
// Check if the current element is equal to
the target
if array[index] equals target: 2(n-1)
// Element found, return the index
return index 1

// If the loop completes without finding the

element, return a value indicating not found
(e.g., -1) 1
return -1 =3n-1

Algorithm An algorithm is a step-by-step procedure for solving a problem in a finite amount of time.
An algorithm is defined as a finite sequence of unambiguous instructions followed to accomplish a
given task.
Data Structure - Is a systematic way of organizing and accessing data, so that data can be used
efficiently Algorithms + Data Structures = Program

Properties of Algorithm-
✓ Input : Each algorithm should have zero or more inputs ✓ Output : The algorithm should produce
correct results. Atleast one output has to be produced ✓ Definiteness : Each instruction should be
clear and unambiguous ✓ Effectiveness : The instructions should be simple and should transform
the given input to the desired output. ✓ Finiteness : The algorithm must terminate after a finite
sequence of instructions

-
Random Access Model
o Algorithms can be measured in a machine-independent way using the Random Access Machine
(RAM) model. o This model assumes a single processor. o In the RAM model, instructions are
executed one after the other, with no concurrent operations. o This model of computation is an
abstraction that allows us to compare algorithms on the basis of performance. o The assumptions
made in the RAM model to accomplish this are: o Each simple operation takes 1 time step. o Loops
and subroutines are not simple operations. o Each memory access takes one time step, and there is
no shortage of memory (we assume we have unbounded memory).

A mixture of natural language and high level programming concepts that describes the main ideas
behind a generic implementation of a data structure and algorithms.
➢ High-level description of an algorithm ➢ More structured than English prose ➢ Less detailed
than a program ➢ Preferred notation for describing algorithms ➢ Hides program design issues

Asymptotic Notations are languages that allow us to analyze an algorithm’s running time by
identifying its behavior as the input size for the algorithm increases. ➢ This is also known as an
algorithm’s growth rate. ➢ Asymptotic notations are the notations used to express the order of
growth of an algorithm and it can be used to compare two algorithms with respect to their
efficiency.
➢ Linear Complexity: Processing time or storage space is directly proportional to the number of
input elements to be processed. ➢ Quadratic complexity: An algorithm is of quadratic complexity if
the processing time is proportional to the square of the number of input elements. ➢ Cubic
complexity: In the case of cubic complexity, the processing time of an algorithm is proportional to
the cube of the input elements. ➢ Logarithmic complexity: An algorithm is of logarithmic complexity
if the processing time is proportional to the logarithm of the input elements. The logarithm base is
typically 2

Techniques employed by algorithms to solve problems – Iterative – Recursion What is Recursion •

The process in which a function calls itself directly or indirectly is called recursion and the
corresponding function is called as recursive function • Define a procedure P that is allowed to make
calls to itself, provided those calls to P are for solving sub-problems of smaller size. Condition for
recursive procedure – A recursive procedure should always define a base case – Base case • Small
sized problem which can be solved by the algorithm directly without using recursion

Recurrence equation – When an algorithm contains a recursive call to itself, its running time can
often be described by a recurrence. A recurrence is an equation or inequality that describes a
function in terms of its value on smaller inputs.
-------------
Insertion at Leaf
Removal at Root

MAX-ASC
MIN-DESC