Performance Analysis - Time and Space Complexity

 

📚 Performance Analysis 

Performance analysis means studying how efficient an algorithm or data structure is.

Mainly, we check two things:

• Time Complexity — How much time (number of operations) the algorithm takes.

• Space Complexity — How much memory (space) the algorithm uses.

✅ Goal:

To predict how the algorithm will behave as the input size grows without running the code.

---

📍 1. Time Complexity

• Measures the amount of time an algorithm takes to complete.

• It is expressed as a function of the input size n.

• We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to express it.

⏳ Why it matters?

Because we want algorithms that are fast even for large inputs.

---

Example for Time Complexity:

Suppose we have a simple loop:

for (int i = 0; i < n; i++) {
    printf("%d ", i);
}

• The loop runs n times.

• Each printf is a constant-time operation.

• So, Time Complexity = O(n) (linear time).

---

Types of Common Time Complexities:

Complexity	Name	Example
O(1)	Constant time	Accessing array element
O(log n)	Logarithmic time	Binary search
O(n)	Linear time	Traversing an array
O(n log n)	Linearithmic time	Merge sort, Heap sort
O(n²)	Quadratic time	Bubble sort, Selection sort
O(2ⁿ)	Exponential time	Solving Tower of Hanoi

📍 2. Space Complexity

• Measures the amount of memory an algorithm needs to complete its execution.

• Memory includes:

  • Variables

  • Data structures (arrays, linked lists)

  • Recursion stack space

✅ Why it matters?

Because limited memory can slow down or crash a program.

---

Example for Space Complexity:

Suppose:

int a, b, c;  // 3 integers

• These use constant memory → Space Complexity = O(1).

Now:

int arr[n];  // array of n elements

• Memory used grows with n → Space Complexity = O(n).

---

📍 Example Combining Both:

Suppose we want to find the sum of all elements in an array:

int sum(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += arr[i];
    }
    return total;
}

• Time Complexity:
  The loop runs n times → O(n).

• Space Complexity:
  Only total variable used (ignoring input array) → O(1).

---

🎯 Summary Table

Aspect	Description	Example
Time Complexity	How long an algorithm runs	O(n), O(log n), O(n²)
Space Complexity	How much memory is needed	O(1), O(n)
Performance Analysis	Study of time and space needs	Done before execution

📚 Why Performance Analysis is Important?

• Helps to choose the best algorithm.

• Helps to predict performance for large inputs.

• Avoids wasting time, memory, and power.

🚀 Simple C Program to Demonstrate Time Complexity

We'll create a program to traverse an array — this has O(n) time complexity.

We'll also measure the execution time using <time.h> functions.

#include <stdio.h>

#include <time.h>

int main() {

    int n;

    printf("Enter the number of elements: ");

    scanf("%d", &n);

    int arr[n];

    

    // Filling the array

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

        arr[i] = i;

    }

    clock_t start, end;

    double cpu_time_used;

    // Start the clock

    start = clock();

    // Traversing the array (O(n) operation) and finding the sum of elements

    int sum = 0;

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

        sum += arr[i];

    }

    // End the clock

    end = clock();

    // Calculate time taken

    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("Sum of elements = %d\n", sum);

    printf("Time taken = %f seconds\n", cpu_time_used);

    return 0;

}

📚 Explanation

• clock_t start, end; — to record start and end time.

• clock() — function returns processor time consumed so far.

• The for loop is O(n) — it depends linearly on the size n.

• We find the difference between start and end to measure how long it took.

✅ You can enter a large value of n (like 1000000) and see how time increases!

🚀 C Program for Bubble Sort with Time Measurement

#include <stdio.h>

#include <time.h>

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

    int temp;

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

        for (int j = 0; j < n - i - 1; j++) {       // comparisons in each pass

            if (arr[j] > arr[j + 1]) {              // swap if elements are out of order

                temp = arr[j];

                arr[j] = arr[j + 1];

                arr[j + 1] = temp;

            }

        }

    }

}

int main() {

    int n;

    printf("Enter number of elements: ");

    scanf("%d", &n);

    int arr[n];

    // Filling array in reverse order to make it worst case

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

        arr[i] = n - i;

    }

    clock_t start, end;

    double cpu_time_used;

    start = clock();

    bubbleSort(arr, n);

    end = clock();

    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("Array sorted using Bubble Sort.\n");

    printf("Time taken = %f seconds\n", cpu_time_used);

    return 0;

}

Output

Enter number of elements: 100

Array sorted using Bubble Sort.

Time taken = 0.000029 seconds

📚 Explanation

• Outer loop: Runs n-1 times.

• Inner loop: On average n/2 times for each pass.

• Thus, total comparisons ≈ n²/2 ⇒ O(n²) time complexity.

• If n = 10000, it will take a longer time compared to simple array traversal (O(n))!

---

📍 Key Observations

Complexity        Program                           Time taken O(n)                   Array Traversal (Sum)    Very fast (even for large n) O(n²)                 Bubble Sort                      Very slow for large n (say n > 5000)

• Bubble Sort is inefficient when n is large because of its quadratic nature.

• That’s why better sorting algorithms like Merge Sort (O(n log n)) are preferred.

---

⚡ Summary

• O(n) — grows linearly, fast for large inputs.

• O(n²) — grows quadratically, very slow when n increases.

• Measuring time helps in understanding real performance, not just theoretical Big-O.