Data Structure and Algorithm: Time & Space Complexity

Time & Space Complexity

1. Time and Space Complexity

2. Introduction In Data Structures and Algorithms (DSA) , time complexity and space complexity are used to analyze the efficiency of an algorithm. They help us determine how well an algorithm performs as the input size increases . 1. Time Complexity Time Complexity measures how the runtime of an algorithm increases with the size of the input. It is expressed using Big-O notation , which describes the upper bound of the growth rate of runtime.

3. Common Time Complexities Notation Name Example O(1) Constant time Accessing an element in an array O(log n) Logarithmic time Binary Search O(n) Linear time Traversing an array O(n log n) Linearithmic Merge Sort, Quick Sort (average) O(n²) Quadratic Bubble Sort, Insertion Sort O(2ⁿ) Exponential Recursive Fibonacci

4. Example // Linear time O(n) void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } }

5. Binary Search

6. 2. Space Complexity Space Complexity measures how much extra memory (apart from input) an algorithm requires during execution. It includes: Fixed part: Memory for constants, program instructions, and fixed-size variables. Variable part: Memory for dynamically allocated variables, recursion stack, etc.

7. Common Space Complexities Notation Example O(1) In-place algorithms (e.g., Bubble Sort) O(n) Storing additional arrays or recursive calls (e.g., Merge Sort) O(n²) Storing a 2D matrix

8. Example of Time and Space Complexity int fib( int n) { int a = 0, b = 1, c; for ( int i = 2; i <= n; i ++) { c = a + b; a = b; b = c; } return b; } Time Complexity: O(n) (loop runs n times) Space Complexity: O(1) (only a few variables used)

9. int fib( int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); } Time Complexity: O(2ⁿ) (due to repeated calculations) Space Complexity: O(n) (function call stack)

10. Example (sum of first N natural numbers) and analyze its time and space complexity #include < stdio.h > int sum_n ( int n) { int total = 0; for ( int i = 1; i <= n; i ++) { total += i ; } return total; } int main() { int n = 5; printf ("Sum = %d\n", sum_n (n)); return 0; }

11. #include < stdio.h > int sum_n_optimized ( int n ) { return n * (n + 1) / 2; } int main() { int n = 5; printf ("Sum = %d\n", sum_n_optimized (n)); return 0; }

12. Exercise 1 (Find Maximum Element) int find_max ( int arr [], int n) { int max = arr [0]; for ( int i = 1; i < n; i ++) { if ( arr [ i ] > max) max = arr [ i ]; } return max; }

13. Exercise 2 (Factorial Using Recursion) int factorial( int n) { if (n == 0) return 1; return n * factorial(n - 1); }

14. Exercise 3 (Nested Loop) void nested_loop ( int n) { for ( int i = 0; i < n; i ++) { for ( int j = 0; j < n; j++ ) { printf ("%d %d\n", i , j); } } }

15. Exercise 4 (Fibonacci (Naive Recursion )) int fib( int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }

16. Exercise 5 (Reverse an Array) void reverse( int arr [], int n) { int temp; for ( int i = 0; i < n/2; i ++) { temp = arr [ i ]; arr [ i ] = arr [n - i - 1]; arr [n - i - 1] = temp; } }

17. String processing String processing refers to the manipulation and analysis of sequences of characters (i.e., strings ) to extract, modify, compare, or search information. Strings are declared as char arrays, for example, char myString [50 ];. The size of the array must be large enough to accommodate the characters.

18. #include < stdio.h > #include < string.h > int main() { char str1[50] = "Hello"; char str2[] = " World!"; char str3[50 ]; printf ("Length of str1: % zu \n", strlen (str1 )); // Get length strcpy (str3 , str1 ); // Copy string printf ("Copied string (str3): %s\n", str3 ); strcat (str1 , str2 ); // Concatenate strings printf ("Concatenated string (str1): %s\n", str1 ); // Compare strings if ( strcmp (str1, str3) == 0) { printf ("str1 and str3 are equal.\n"); } else { printf ("str1 and str3 are not equal.\n"); } return 0; }

19. Real-Life Applications of DSA Application Area Role of DSA Web Search (e.g., Google) Algorithms (e.g., PageRank) sort and retrieve search results fast. Social Media (e.g., Facebook) Graphs represent friends/followers; hashing speeds up data access. Online Shopping (e.g., Amazon) Sorting and searching products use trees, arrays, and binary search. Navigation (e.g., Google Maps) Graph algorithms find shortest paths between locations. Banking and ATMs Queues manage transactions; trees handle account data securely. Hospital Management Priority queues schedule patients; linked lists manage records. Music/Video Streaming (e.g., YouTube) Caches (hash tables) store most-used data; recommendations use algorithms. Gaming Trees and graphs manage game levels and movements. Mobile Apps Efficient apps use stacks, queues, arrays for fast operations. AI and Machine Learning Algorithms analyze data; trees and graphs model decisions.