Find Time complexity in O(n)

void fun1(int n) { void fun2(int n) { void fun3(int n) {

int i, j; int i, j, k; int i, j;
for (i = 1; i <= n; i++) for (i = 1; i <= n; i++) for (i = 1; i <= n; i *= 2)
for (j = 1; j <= i; j *= 2) for (j = 1; j <= i; j++) for (j = 1; j <= i; j++)
printf("Coding is for (k = 1; k <= j; k++) printf("Hello
fun\n"); printf("Algorithms World\n");
} rock\n"); }
}

void fun4(int n) { void fun5(int n) { void fun6(int n) {

int i, j; int i, j, k; int i, j;
for (i = n; i > 0; i /= 2) for (i = 1; i <= n; i++) for (i = 1; i <= n; i++)
for (j = i; j > 0; j--) for (j = 1; j <= i; j++) for (j = 1; j <= n; j *= 2)
printf("Data for (k = 1; k <= j * j; printf("Coding\n");
Structures\n"); k++) for (i = n; i > 0; i /= 2)
} printf("Keep it printf("Practice\n");
simple\n"); }
}

void fun7(int n) { void fun8(int n) { void fun9(int n) {

int i, j, k; int i, j, k; int i, j;
for (i = 1; i <= n; i *= 3) for (i = n; i > 0; i /= 3) for (i = 1; i <= n; i += 2)
for (j = 1; j <= n; j++) for (j = 1; j <= i; j++) for (j = i; j <= n; j *= 2)
for (k = j; k > 0; k--) for (k = 1; k <= j * j; printf("Success\n");
printf("Learn\n"); k++) }
} printf("Focus\n");
}
 • Find the time function f(n) for the following code and then find the value of C and
n for which f(n)=O(n)is valid.

int arr[n], length = 0;

for(int i = 0; i < n; i++) {
arr[i] = 0;
for(int j = 0; j < n-1; j++) {
arr[i] = arr[j] + arr[j+1];
length++;
}
}
Memory Representation of array:

Address of A[Index] = B + W * (Index – LB)

Where:

• Index = The index of the element whose address is to be found (not the value of the
element).
• B = Base address of the array.
• W = Storage size of one element in bytes.
• LB = Lower bound of the index (if not specified, assume zero).

Example: Given the base address of an array A[1300 ………… 1900] as 1020 and the
size of each element is 2 bytes in the memory, find the address of A[1700].

Given:

• Base address (B) = 1020

• Lower bound (LB) = 1300
• Size of each element (W) = 2 bytes
• Index of element (not value) = 1700

Formula used:
Address of A[Index] = B + W * (Index – LB)
Address of A[1700] = 1020 + 2 * (1700 – 1300)
= 1020 + 2 * (400)
= 1020 + 800
Address of A[1700] = 1820
IN 2D ARRAY:

1. Row-Major Order:

In row-major order, elements of the array are stored row by row in memory.
The formula to calculate the address of an element A[i][j] in a 2D array stored in row-major order is:

Address of A[i][j] = B + W × ((i - LR) × NC + (j - LC))

Where:
- B = Base address of the array (the address of the first element).
- W = Size of each element in bytes.
- i = Row index.
- j = Column index.
- LR = Lower bound of row index (default is 0 if not specified).
- LC = Lower bound of column index (default is 0 if not specified).
- NC = Number of columns in the array.

2. Column-Major Order:

In column-major order, elements are stored column by column in memory.

The formula to calculate the address of an element A[i][j] in a 2D array stored in column-major order is:

Address of A[i][j] = B + W × ((j - LC) × NR + (i - LR))

Where:
- B, W, i, j, LR, and LC are the same as above.
- NR = Number of rows in the array.

Example:

Let's say we have a 2D array A[4][5] (4 rows and 5 columns) stored in row-major order. The base address
B is 1000, and each element takes 2 bytes of memory.

Now, let's find the memory address of element A[2][3].

Given:
- Base address B = 1000
- Size of each element W = 2 bytes
- Number of columns NC = 5
- Lower bounds LR = LC = 0
- Row index i = 2
- Column index j = 3
Using the row-major order formula:
Address of A[2][3] = 1000 + 2 × ((2 - 0) × 5 + (3 - 0))

First, calculate the term inside the parentheses:

(2 × 5) + 3 = 10 + 3 = 13
Now, multiply by the size of each element (2 bytes):
2 × 13 = 26
Finally, add this to the base address:
1000 + 26 = 1026

Result:

The address of A[2][3] in row-major order is 1026.

Algorithm: Matrix Multiplication

1. Input: Two matrices A[m][n] and B[n][p].
2. Output: Resultant matrix C[m][p] after multiplication.

Steps:
1. Initialize the resultant matrix C with dimensions m × p. Set all elements of C to 0.
C[i][j] = 0 for all i, j
2. Loop through the rows of matrix A using index i (from 0 to m-1).
3. Loop through the columns of matrix B using index j (from 0 to p-1).
4. Compute the dot product of the i-th row of A and the j-th column of B.
5. Accumulate the product into C[i][j].
6. Once all iterations are complete, matrix C contains the result.
PSEUDO CODE FOR MATRIX MULTIPLICATION:

1. Array Traversal:
Algorithm:

1. Start with an array A of size n.

2. Set an index variable i to 0.
3. While i < n:
a. Access the element A[i].
b. Print or process the element A[i].
c. Increment i by 1.
4. End.

Pseudocode:

ArrayTraversal(A, n)
for (i = 0; i<n; i++)
Access A[i]
Process A[i]
end for
2. Array Insertion:
Algorithm:

1. Start with an array A of size n and the position pos where you want to insert a new element.
2. If the array is full, return an error or resize the array.
3. Shift all elements from index pos to n-1 one position to the right.
4. Insert the new element at position pos.
5. Increase the size of the array by 1.
6. End.

Pseudocode:

ArrayInsertion(A, n, pos, element)

for( i = n-1; i>pos; i--)
A[i+1] = A[i]

end for
A[pos] = element
n=n+1

3. Array Deletion:
Algorithm:

1. Start with an array A of size n and the position pos of the element to be deleted.
2. Shift all elements from index pos+1 to n-1 one position to the left.
3. Decrease the size of the array by 1.
4. End.

Pseudocode:

ArrayDeletion(A, n, pos)
for (i = pos; i<n; i++)
A[i] = A[i+1

end for
n=n-1
Binary Search:
cc

Pseudocode:
Explanation of Time Complexity O(log n)

Binary Search operates by dividing the search range in half during each step, which is the key
reason why its time complexity is O(log⁡n)O(\log n)O(logn). Let's break down the
mathematical reasoning behind it:

Step-by-Step Breakdown:

1. Initial Search Range (n elements):

o Initially, we start with a sorted array of n elements.
o We check the middle element to see if it matches the target. If not, we either move to
the left or right half.
2. Each Iteration Halves the Range:
o In each step, we eliminate half of the search space.
o So after 1 step, the remaining elements are n/2.
o After 2 steps, the remaining elements are n/4.
o After 3 steps, the remaining elements are n/8, and so on.
3. Generalize the Halving Process:
o After k steps, the number of remaining elements is n/2^k.
4. When Does the Search End?
o The search continues until the remaining number of elements becomes 1 (i.e., when we
reach a single element).
o This gives the equation: n/2^k = 1
o Solving for k = log2 n
o Therefore, the number of steps required is k = log2n.

Steps to Find Element Using Binary Search for (n = 10^6):

• Let's calculate how many steps it takes to search through a sorted array with n = 10^6
elements using binary search.
o Binary search reduces the search space by half in each step.
o The number of steps required is approximately log₂(n).

For n = 10^6, the number of steps required is:

log₂(10^6) ≈ log₂(2^20) = 20 steps.

Bubble Sort:
Algorithm:

Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and
swapping them if they are in the wrong order. This process is repeated until the list is sorted.

1. Start with an unsorted array of size n.

2. For each element from the first to the last, repeat the following steps:
o Compare the current element with the next element.
o If the current element is greater than the next element, swap them.
3. After each pass, the largest unsorted element is moved to its correct position.
4. Repeat this process until no swaps are needed (i.e., the array is sorted).

Pseudocode:

BubbleSort(A, n)
1. for i = 0 to n-1:
a. for j = 0 to n-i-2:
i. if A[j] > A[j+1]:
- Swap A[j] and A[j+1]
2. End.

Time complexity: O(n)

If the total number of steps in Bubble Sort is 21, how many elements are in the array?

The number of comparisons in Bubble Sort can be expressed as the sum of the first n−1 natural
numbers:

Total Comparisons=n(n−1)/2

Where n is the number of elements in the array.

Given that the total number of comparisons is 21:

n(n−1)/2 = 21

Multiplying both sides by 2:

n(n−1)=42
n^2 – n – 42 =0

So, n=7.

Answer:

If there are 21 total steps (comparisons), the array contains 7 elements.

Selection Sort:
Algorithm for Selection Sort:

1. Input: An array A of n elements.

2. Output: A sorted array in ascending order.

Steps:

1. Start with the first element (index 0).

2. Find the smallest element in the unsorted part of the array.
3. Swap this smallest element with the element at the beginning of the unsorted part.
4. Move the boundary between the sorted and unsorted parts one element to the right.
5. Repeat until the array is sorted.

Pseudocode for Selection Sort:

SelectionSort(A, n)

for i = 0 to n-1 do
minIndex = i
for j = i+1 to n-1 do
if A[j] < A[minIndex] then
minIndex = j
end if
end for

Swap(A[i], A[minIndex])
end for
end
Example:

Consider an unsorted array: A = [64, 25, 12, 22, 11].

Step-by-step selection sort process:

1. Find the smallest element in the array (11), and swap it with the first element.
o Array becomes: [11, 25, 12, 22, 64]
2. Find the smallest element in the unsorted portion (12), and swap it with the second element.
o Array becomes: [11, 12, 25, 22, 64]
3. Find the smallest element in the remaining unsorted portion (22), and swap it with the third
element.
o Array becomes: [11, 12, 22, 25, 64]
4. No further swaps are needed, as the array is now sorted.

Insertion Sort:
Insertion Sort Algorithm:

1. Input: An array A of size n.

2. Start from the second element A[1] and compare it with the previous elements.
3. Move all elements greater than A[i] to one position ahead of their current position.
4. Insert the current element A[i] in its correct position.
5. Repeat steps 2 to 4 for all elements in the array.

Pseudocode:

InsertionSort(A, n)
for i = 1 to n-1 do
key = A[i]
j = i - 1

while j >= 0 and A[j] > key do

A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
end for