Please Type your answer and reasoning

Part 2: Complexity Analysis

For Ex.1-3, along with reasoning, analyze both runtime and space complexity using Big O for the best, average, and worst cases (relative to input size n) . Type your answer and reasoning

Ex.1: Linear search algorithm to find a specific element (with value x) in an array: (n = the size of the array)

int linearSearch(int arr[], int n, int x) { for (int i = 0; i < n; i++) { if (arr[i] == x); return i; } return -1; }

Ex.2: Bubble sort to sort an array: (n = the size of the array)

void bubbleSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { bool swapped = false; for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; swapped = true; } } 

if (swapped == false) break; } }

Ex.3: Remove a node from the end of a singly list: (n = the size of the list)

struct Node { int data; struct Node* next; };

struct Node* head = NULL; 

void remove_end() { if (head == NULL) return; if (head->next = = NULL) { free(head); head = NULL; return; } struct Node* current = head; while (current->next->next != NULL) current = current->next; free(current->next); current->next = NULL; }