In time complexity analysis, we consider three cases:

- Best case: This reflects the situation in which the algorithm operates best, with the least amount of input and no unique circumstances. The algorithm's performance lower bound is shown by the best-case time complexity.

- Average case: This illustrates how an algorithm should perform given a variety of inputs. It determines the typical number of operations carried out while taking the input distribution into account. A more accurate estimation of an algorithm's performance is provided by its average-case time complexity.

- Worst case: This illustrates the situation in which the algorithm executes the greatest number of operations while taking into account the largest input possible or any special circumstances. The algorithm's maximum performance is indicated by the worst-case time complexity.

Examples of simple codes and their time complexity calculations

Following are some simple codes with their time complexities:

1. Linear Search:

Code:

int linearSearch(int arr[], int n, int target) {

for (int i = 0; i < n; i++) {

if (arr[i] == target) {

return i;

}

}

return -1;

}

Time Complexity: O(n)

The code performs a linear search through the array arr of size n. In the worst case, it may have to iterate through the entire array of size n to find the target element. Hence the time complexity is O(n).

2. Bubble Sort:

Code:

void bubbleSort(int arr[], int n) {

for (int i = 0; i < n-1; i++) {

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;

}

}

}

}

Time Complexity: O(n^2)

The code implements the Bubble Sort algorithm to sort the array arr of size n. The two nested loops iterate through the array multiple times, comparing and swapping adjacent elements if necessary. Since the loops are nested, time complexity is O(n*n)= O(n^2).

3. Binary Search:

Code:

int binarySearch(int arr[], int low, int high, int target) {

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == target) {

return mid;

}

if (arr[mid] < target) {

low = mid + 1;

} else {

high = mid - 1;

}

}

return -1;

}

Time Complexity: O(log n)

The code performs a binary search on the sorted array arr within the range low to high to find the target element. At each step, it reduces the search range by half, resulting in a logarithmic time complexity of O(log n).

How to calculate the time complexity of different algorithms (recursive, divide and conquer, greedy, etc.) (with examples)

1. Recursive Algorithms:

- Identify the number of recursive calls and their sizes and write the recurrence relation.

- Solve the recurrence relation to obtain the time complexity.

Example: Fibonacci sequence recursively

Code:

int fibonacci(int n) {

if (n <= 1) {

return n;

} else {

return fibonacci(n - 1) + fibonacci(n - 2);

}

}

In this case, the recurrence relation is T(n) = T(n-1) + T(n-2) + O(1). The algorithm makes two recursive calls with decreasing input sizes, and each call performs constant work. By solving this recurrence relation, the time complexity is exponential, O(2^n).

2. Divide and Conquer Algorithms:

- Identify the number of subproblems and the size of each subproblem.

- Write and solve the recurrence relation.

Example: Merge Sort

Code:

void merge(int arr[], int low, int mid, int high) {

// Merge two sorted subarrays

}

void mergeSort(int arr[], int low, int high) {

if (low < high) {

int mid = (low + high) / 2;

mergeSort(arr, low, mid);

mergeSort(arr, mid + 1, high);

merge(arr, low, mid, high);

}

}

The time complexity of Merge Sort can be calculated by analyzing the number of comparisons and the size of the input array. The recurrence relation for Merge Sort is T(n) = 2T(n/2) + O(n), representing the two recursive calls and the merging step. By solving this recurrence relation using the Master Theorem or the recurrence tree method, the time complexity of Merge Sort is O(n log n).

3. Greedy Algorithms:

- Analyze each step of the algorithm.

- Determine whether the greedy choice results in the optimal solution.

- Calculate the total number of steps or operations.

Example: Activity Selection Problem.

Code:

struct Activity {

int start;

int finish;

};

int activitySelection(Activity arr[], int n) {

sort(arr, arr + n, [](Activity a, Activity b) {

return a.finish < b.finish;

});

int count = 1;

int prevFinish = arr[0].finish;

for (int i = 1; i < n; i++) {

if (arr[i].start >= prevFinish) {

count++;

prevFinish = arr[i].finish;

}

}

return count;

}

The time complexity of the Greedy Activity Selection algorithm is determined by the sorting step and the linear scan through the sorted array. Sorting the array of activities takes O(n log n) time, and the linear scan takes O(n) time. Therefore, the overall time complexity is O(n log n).