UNIT-1

GROWTH OF FUNCTIONS , RECURRENCE

RELATION

1. THE CONSTANT FUNCTION:- The simplest function we can think of is the

constant function. This is the function,
f (n) = c, for some fixed constant c.

2. THE LOGARITHM FUNCTION:- f(n)=logbn for some constant b>1

this function is defined as:x=logbn iff bx=n

b -> base

o product rule: logb mn = logb m + logb n.

o quotient rule: logb m/n = logb m - logb n.
o power rule: logb mn = n logb m.
o change of base rule: loga b = (logc b) / (logc a)
3. LINEAR FUNCTION:- f(n)=n , Linear function f assigns the value n itself.
4. N-LOG-N FUNCTION:- f(n)=n Function assigns to an input n the values of n
times the logarithmic base.
5.
QUADRATIC FUNCTION:- f(n)=n2
6.
CUBIC FUNCTION:- f(n)=n3
7.
POLYNOMIAL FUNCTION:- f(n)=a0 + a1n+a2n2+….+adnd
A0 , a1……….. are coefficients of polynomial.
𝑛
𝑛(𝑛+!)
𝑖=
SUMMATION NOTATIONS:- ∑ 2
𝑖=0

8. EXPONENTIAL FUNCTION:- f(n) = bn

b-> +ve constant/base n-> exponent.
Exponent rules:-
(ba )c = bac
babc = b a+c
ba/bc = b a-c

ASCENDING ORDER OF FUNCTION(ACC. TO RUNNING TIME):-

exponential<cubic<quadratic<nlogn<linear<logarithmic<constant.
RECURSION:-

Recurrence Relation

THE SUBSTITUTION METHOD FOR SOLVING RECURRENCES:-

T(n) = n * T(n-1)
Termination condition:
=> n = 1
Iterations:
T(n) = n * T(n-1) -------------- ①
T(n-1) = (n-1) * T(n-2) -------- ②
T(n-2) = (n-2) * T(n-3) -------- ③
Substitute ② in eqn ①
T(n) = n * T(n-1) * T(n-2)
T(n) = n * (n-1) * T(n-2) * T(n-3)
Now putting ③
T(n) = n * (n-1) * (n-2) * T(n-3) * ...
T(n) = n * (n-1) * (n-2) * (n-3) * ... * T(1)
T(n) = n * (n-1) * (n-2) * (n-3) * ... * 1
=> n * (n-1) * (n-2) * (n-3) ... 3 * 2 * 1
=> n * n(1 - 1/n) * n(1 - 2/n) * ... n(3/n) * n(2/n) * n(1/n)
= O(n^n) dlt

QUES 2.

2T(n) = 2T(n/2) + n
Termination condition:
=> n = 1
Substitutions:
2T(n/2) = 2T(n/4) + n/2
2T(n/4) = 2T(n/8) + n/4

By substituting, we get:
2T(n) = 2^2 * T(n/4) + 2 * n
2^2 * T(n/4) = 2^3 * T(n/8) + 2^2 * (n/4)
= 2^3 * T(n/8) + 2n/2 = 2^3 * T(n/8) + 2n
Continuing this pattern:
= 2^k * T(n/2^k) + k * n
When n/2^k = 1,
n = 2^k => k = log(n)
Thus, T(n) = O(n log n)

QUESTION 3.
3) T(n) = T(n-1) + log n --------------(1)
T(n-1) = T(n-2) + log (n-1) --------(2)
T(n-2) = T(n-3) + log (n-2) --------(3)
Substitute (2) in (1)
T(n) = T(n-2) + log (n-1) + log n
Now Substitute (3)
T(n) = T(n-3) + log (n-2) + log (n-1) + log n
T(n) = T(n-4) + log (n-3) + log (n-2) + log (n-1) + log n
K times
T(n-k) + log (n') (n-1) + log (n') (n-2) + log (n') (n-3) + ... + log (n') (n-k+1)
Put n-k=1
n=k
Putting k=n
=> T(1) + log (n') (n+1) + log (n') (n+2) + log (n') (n+3) + ... + log (n)
=> T(1) + log (1) + log (2) + log (3) + ... + log (n)
1 + log (1, 2, 3, 4, ... , n)
1 + log (n!)
1 + log (n!) ≈ 1 + n log n
= O(n log n)

RECURSIVE TREE METHOD

The Recursion Tree Method is a way of solving recurrence relations. In this method, a
recurrence relation is converted into recursive trees. Each node represents the cost incurred at
various levels of recursion. To find the total cost, costs of all levels are summed up.
Steps to solve recurrence relation using recursion tree method:

1. Draw a recursive tree for given recurrence relation

2. Calculate the cost at each level and count the total no of levels in the recursion tree.
3. Count the total number of nodes in the last level and calculate the cost of the last level

4. Sum up the cost of all the levels in the recursive tree

Note: If summing up all the levels becomes complex, we can find an upper bound by
considering a perfectly full tree and / or an infinite geometrical series (the ratio is typically
less than 1).

Question 1:

T(n) = 2T(n/2) + c

Solution:

• Step 1: Draw a recursive tree

Question 1:

T(n) = 2T(n/2) + c

Solution:

• Step 1: Draw a recursive tree

• Step 2: Calculate the work done or cost at each level and count total no of levels in
recursion tree
Recursive Tree with each level cost

S
MASTER METHOD/THEOREM:-

Given a recurrence of the form T(n) = aT(n/b) + f(n),

for constants a ≥ 1 and b > 1 with f asymptotically positive, the following statements are
true:

Case 1:

If f(n) = O(n^(log_b(a) - ε)) for some ε > 0, then T(n) = Θ(n^(log_b(a))).

Case 2:

If f(n) = Θ(n^(log_b(a))), then T(n) = Θ(n^(log_b(a)) * log(n)).

Case 3:

If f(n) = Ω(n^(log_b(a) + ε)) for some ε > 0 and a*f(n/b) ≤ c*f(n) for some c < 1, for all
sufficiently large n,

then T(n) = Θ(f(n)).

 Unit 2
Arrays, Linked Lists, Stacks, Queues, Deques
ARRAYS:-

Arrays are a type of list that consist of items of the same type (Data Structure).

• Example:
A bag containing only potatoes (all items are of the same type).

• 10,000 integers → Array of int

• 10,000 characters → Array of char

• CustomDatatype:
If we define a custom datatype, e.g., "Car", it can store 10,000 values → Array of car
type.

Memory Representation:
The values stored in an array in memory are located in continuous memory locations (all
elements are stored one after another).
Example:
A 5-integer array:

Array: [3,5,9,2,11]
• Memory locations (addresses): 100, 104, 108, 112, 116, 120 (each integer takes 4
bytes).
• Accessing element:- All elements in the array can be accessed using an index.

Why Do We Need Arrays?

To store multiple values of the same type in one variable, we need an array.
Implementation:

1. Declaration of Variable:

Declaration of a single variable a.

Memory block is allocated to store one integer value.

2. Declaration of Array:

Parts of Declaration:

• int: Data type of the array.

• arr: Name of the array.

• [10]: Size of the array (can hold 10 elements).

The array describes the address of the first memory location and the index positions are
used to access elements.

Key Notes:

1. Arrays allow the storage of multiple values in contiguous memory.

2. Each index corresponds to a specific element.

INITIALIZING ALL ELEMENTS OF THE ARRAY TO ANY SPECIFC VALUE.
INSERTION SORT ALGORITHM
Insertion sort is a simple sorting algorithm that works by iteratively inserting each
element of an unsorted list into its correct position in a sorted portion of the list.

CODE:

OUTPUT:-
arr = {23, 1, 10, 5, 2}
EXPLANATION OF CODE OF INSERTION SORT:-
Initial:
• Current element is 23
• The first element in the array is assumed to be sorted.
• The sorted part until 0th index is : [23]
First Pass:
• Compare 1 with 23 (current element with the sorted part).
• Since 1 is smaller, insert 1 before 23 .
• The sorted part until 1st index is: [1, 23]
Second Pass:
• Compare 10 with 1 and 23 (current element with the sorted part).
• Since 10 is greater than 1 and smaller than 23 , insert 10 between 1 and 23 .
• The sorted part until 2nd index is: [1, 10, 23]
Third Pass:
• Compare 5 with 1 , 10 , and 23 (current element with the sorted part).
• Since 5 is greater than 1 and smaller than 10 , insert 5 between 1 and 10
• The sorted part until 3rd index is : [1, 5, 10, 23]
Fourth Pass:
• Compare 2 with 1, 5, 10 , and 23 (current element with the sorted part).
• Since 2 is greater than 1 and smaller than 5 insert 2 between 1 and 5 .
• The sorted part until 4th index is: [1, 2, 5, 10, 23]
Final Array:
• The sorted array is: [1, 2, 5, 10, 23]

Time Complexity of Insertion Sort

• Best case: O(n) , If the list is already sorted, where n is the number of elements
in the list.
• Average case: O(n 2 ) , If the list is randomly ordered
• Worst case: O(n 2 ) , If the list is in reverse order
Space Complexity of Insertion Sort
• Auxiliary Space: O(1), Insertion sort requires O(1) additional space, making it a
space-efficient sorting algorithm.

Advantages of Insertion Sort:

• Simple and easy to implement.
• Stable sorting algorithm.
• Efficient for small lists and nearly sorted lists.
• Space-efficient as it is an in-place algorithm.
• Adoptive. the number of inversions is directly proportional to number of swaps.
For example, no swapping happens for a sorted array and it takes O(n) time only.

Disadvantages of Insertion Sort:

• Inefficient for large lists.
• Not as efficient as other sorting algorithms (e.g., merge sort, quick sort) for most
cases.

Applications of Insertion Sort:

Insertion sort is commonly used in situations where:
• The list is small or nearly sorted.
• Simplicity and stability are important.
• Used as a subroutine in Bucket Sort
• Can be useful when array is already almost sorted (very few inversions)
• Since Insertion sort is suitable for small sized arrays, it is used in Hybrid Sorting
algorithms along with other efficient algorithms like Quick Sort and Merge Sort.
When the subarray size becomes small, we switch to insertion sort in these
recursive algorithms. For example IntroSort and TimSort use insertions sort.
Linked List Data Structure
A linked list is a fundamental data structure in computer science. It mainly allows
efficient insertion and deletion operations compared to arrays. Like arrays, it is also used to
implement other data structures like stack, queue and deque. Here’s the comparison of Linked
List vs Arrays

Linked List:

• Data Structure: Non-contiguous

• Memory Allocation: Typically allocated one by one to individual elements

• Insertion/Deletion: Efficient

• Access: Sequential

Array:

• Data Structure: Contiguous

• Memory Allocation: Typically allocated to the whole array

• Insertion/Deletion: Inefficient
• Access: Random

Singly Linked List Tutorial

A singly linked list is a fundamental data structure, it consists of nodes where each node
contains a data field and a reference to the next node in the linked list. The next of the last
node is null, indicating the end of the list. Linked Lists support efficient insertion and deletion
operations.
Understanding Node Structure

In a singly linked list, each node consists of two parts: data and a pointer to the next node. This
structure allows nodes to be dynamically linked together, forming a chain-like sequence.
In this example, the Node class contains an integer data field (data) to store the information
and a pointer to another Node (next) to establish the link to the next node in the list.

Operations on Singly Linked List

• Traversal

• Searching

• Length

• Insertion:
o Insert at the beginning

o Insert at the end

o Insert at a specific position

• Deletion:

o Delete from the beginning

o Delete from the end

o Delete a specific node

Traversal of Singly Linked List

Traversal involves visiting each node in the linked list and performing some operation on the
data. A simple traversal function would print or process the data of each node.

Step-by-step approach:

• Initialize a pointer current to the head of the list.

• Use a while loop to iterate through the list until the current pointer reaches NULL.

• Inside the loop, print the data of the current node and move the current pointer to the
next node.

Below is the function for traversal in singly Linked List:

Searching in Singly Linked List

Searching in a Singly Linked List refers to the process of looking for a specific element or
value within the elements of the linked list.

Step-by-step approach:

1. Traverse the Linked List starting from the head.

2. Check if the current node's data matches the target value.

• If a match is found, return true.

3. Otherwise, Move to the next node and repeat steps 2.

4. If the end of the list is reached without finding a match, return false.

Below is the function for searching in singly linked list:

Length of Singly Linked List

Finding Length in Singly Linked List refers to the process of determining the total number of
nodes in a singly linked list.
Step-by-step approach:

• Initialize a counter length to 0.

• Start from the head of the list, assign it to current.

• Traverse the list:

o Increment length for each node.

o Move to the next node (current = current->next).

• Return the final value of length.

Below is the function for finding length in Singly Linked List:
Insertion in Singly Linked List

Insertion is a fundamental operation in linked lists that involves adding a new node to the list.
There are several scenarios for insertion:

a) Insertion at the Beginning of Singly Linked List:

Step-by-step approach:

• Create a new node with the given value.

• Set the next pointer of the new node to the current head.

• Move the head to point to the new node.

• Return the new head of the linked list.
Below is the function for insertion at the beginning of singly linked list:

b. Insertion at the End of Singly Linked List:

To insert a node at the end of the list, traverse the list until the last node is reached, and then
link the new node to the current last node-

Step-by-step approach:
• Create a new node with the given value.

• Check if the list is empty:

o If it is, make the new node the head and return.

• Traverse the list until the last node is reached.

• Link the new node to the current last node by setting the last node's next pointer to the
new node.

Below is the function for insertion at the end of singly linked list:
c. Insertion at a Specific Position of the Singly Linked List:

To insert a node at a specific position, traverse the list to the desired position, link the new node
to the next node, and update the links accordingly.

We mainly find the node after which we need to insert the new node. If we encounter a NULL
before reaching that node, it means that the given position is invalid.

Below is the function for insertion at a specific position of the singly linked list:
Deletion in Singly Linked List

Deletion involves removing a node from the linked list. Similar to insertion, there are different
scenarios for deletion:

a. Deletion at the Beginning of Singly Linked List:

To delete the first node, update the head to point to the second node in the list.

Steps-by-step approach:
• Check if the head is NULL.

o If it is, return NULL (the list is empty).

• Store the current head node in a temporary variable temp.

• Move the head pointer to the next node.

• Delete the temporary node.

• Return the new head of the linked list.

Below is the function for deletion at the beginning of singly linked list:
b. Deletion at the End of Singly Linked List:

To delete the last node, traverse the list until the second-to-last node and update its next field
to None.

Step-by-step approach:

• Check if the head is NULL.

o If it is, return NULL (the list is empty).

• Check if the head's next is NULL (only one node in the list).

o If true, delete the head and return NULL.

• Traverse the list to find the second last node (second_last).

• Delete the last node (the node after second_last).

• Set the next pointer of the second last node to NULL.

• Return the head of the linked list.

Below is the function for deletion at the end of singly linked list:
c. Deletion at a Specific Position of Singly Linked List:

To delete a node at a specific position, traverse the list to the desired position, update the links
to bypass the node to be deleted.

Step-by-step approach:

• Check if the list is empty or the position is invalid, return if so.

• If the head needs to be deleted, update the head and delete the node.

• Traverse to the node before the position to be deleted.

• If the position is out of range, return.

• Store the node to be deleted.

• Update the links to bypass the node.

• Delete the stored node.

Below is the function for deletion at a specific position of singly linked list: