Concept of time complexity:
Time Complexity Analysis is a way to estimate how the runtime of an algorithm increases as the size of the input grows. It helps in understanding the efficiency of an algorithm and is essential for designing scalable and optimal solutions. Below is an explanation of the steps involved in analyzing the time complexity of an algorithm:
1. Understand the Algorithm
Input Size (n): Identify the variable(s) that define the size of the input, usually denoted as n.
Operations: Understand the basic operations or steps the algorithm performs, such as loops, conditionals, or recursive calls.
2. Count the Operations
Count how many times each operation is executed as a function of n.
For loops, count the iterations.
For nested loops, calculate the product of the iterations of the loops.
For recursions, analyze the number of recursive calls.
3. Express the Complexity
Combine the counts from all parts of the algorithm into a single expression that represents the total number of operations as a function of n.
4. Classify the Growth Rate:
Use Big-O Notation to express the upper bound of the algorithm's runtime. It describes the growth rate of the runtime in terms of the largest factor in the expression. Common complexities include:
Importance of Time Complexity Analysis
1. Comparing Algorithms: Helps choose the most efficient algorithm for a problem.
2. Predicting Performance: Guides scaling decisions and hardware requirements.
3. Optimizing Code: Helps identify bottlenecks and improve efficiency.
Algorithms Practiced in The Lab :
1) Array Sum Calculation
Description: Calculate the sum of elements in an array.
Code:
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
#define SIZE 1000
#define ITER 10000
void find_sum(int a[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum = sum + a[i];
}
}
int main() {
clock_t start, endt;
double duration;
int a[SIZE];
srand(42); // Random seed
for (int i = 0; i < SIZE; i++) {
a[i] = rand() % 1000;
}
start = clock();
for (int i = 0; i < ITER; i++) {
find_sum(a, SIZE);
}
endt = clock();
duration = (double)(endt - start) / CLOCKS_PER_SEC;
cout << "Time taken in seconds is " << duration / ITER;
return 0;
}
OUTPUT:
Time taken in seconds is 6.2e-006
Execution Time: 0.353 s
2) Linear and Binary Search
Description: Implement and compare Linear Search and Binary Search.
Linear Search checks each element in a list sequentially.
Binary Search divides the list in half to search for the target element.
Code:
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
#define SIZE 5000
#define ITER 10000
// Linear Search Function
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Target found
}
}
return -1; // Target not found
}
// Binary Search Function
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid; // Target found
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // Target not found
}
// Selection Sort Function (for sorting array before Binary Search)
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
// Function to Measure Time for Linear and Binary Search
void measureSearchTime(int n) {
int *arr = new int[n];
srand(42); // Random seed
for (int i = 0; i < n; i++) arr[i] = rand() % 5000;
int target = arr[0]; // Best-case target (first element)
clock_t start, end;
double duration;
// Linear Search - Best Case
start = clock();
for (int i = 0; i < ITER; i++) {
linearSearch(arr, n, target);
}
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
cout << "Linear Search (Best Case) for " << n << " elements: " << duration / ITER << " seconds" << endl;
// Linear Search - Average Case
target = arr[rand() % n]; // Random element for average case
start = clock();
for (int i = 0; i < ITER; i++) {
linearSearch(arr, n, target);
}
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
cout << "Linear Search (Average Case) for " << n << " elements: " << duration / ITER << " seconds" << endl;
// Linear Search - Worst Case
target = -1; // Target not in array
start = clock();
for (int i = 0; i < ITER; i++) {
linearSearch(arr, n, target);
}
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
cout << "Linear Search (Worst Case) for " << n << " elements: " << duration / ITER << " seconds" << endl;
// Sort array for Binary Search
selectionSort(arr, n);
// Binary Search - Best Case
target = arr[n / 2]; // Middle element for best case
start = clock();
for (int i = 0; i < ITER; i++) {
binarySearch(arr, n, target);
}
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
cout << "Binary Search (Best Case) for " << n << " elements: " << duration / ITER << " seconds" << endl;
// Binary Search - Average Case
target = arr[rand() % n]; // Random element for average case
start = clock();
for (int i = 0; i < ITER; i++) {
binarySearch(arr, n, target);
}
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
cout << "Binary Search (Average Case) for " << n << " elements: " << duration / ITER << " seconds" << endl;
// Binary Search - Worst Case
target = -1; // Target not found
start = clock();
for (int i = 0; i < ITER; i++) {
binarySearch(arr, n, target);
}
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
cout << "Binary Search (Worst Case) for " << n << " elements: " << duration / ITER << " seconds" << endl;
delete[] arr; // Free allocated memory
}
int main() {
measureSearchTime(SIZE);
return 0;
}
Output:
Linear Search (Best Case) for 5000 elements: 0 seconds
Linear Search (Average Case) for 5000 elements: 1.33e-005 seconds
Linear Search (Worst Case) for 5000 elements: 1.58e-005 seconds
Binary Search (Best Case) for 5000 elements: 0 seconds
Binary Search (Average Case) for 5000 elements: 5e-007 seconds
Binary Search (Worst Case) for 5000 elements: 0 seconds
KEY TAKE-AWAYS
Linear Search:
Best Case: O(1)
Worst Case: O(n)
Average Case: O(n)
Binary Search:
Best Case: O(1)
Worst Case: O(log n)
Average Case: O(log n)