The efficiency of a program is primarily measured in terms of time and space complexity. It helps assess how a program performs as the input size grows.

1. Time Complexity:

• Definition: Time complexity refers to the amount of operations made by an algorithm to run as a function of the length of the input.
• Common Time Complexities:
  • O(1): Constant time (e.g., accessing array elements).
  • O(log n): Logarithmic time (e.g., binary search).
  • O(n): Linear time (e.g., traversing an array).
  • O(n log n): Linearithmic time (e.g., merge sort).
  • O(n²): Quadratic time (e.g., bubble sort).
  • O(2ⁿ): Exponential time (e.g., recursive Fibonacci).
• Big-O Notation: Used to express the upper bound of the time complexity (worst-case scenario).
• Theta (Θ): Represents the average time complexity.
• Omega (Ω): Represents the best-case time complexity.

2. Space Complexity:

• Definition: Space complexity is the amount of memory an algorithm uses as a function of input size.
• Categories:
  • Auxiliary space: Extra space used, excluding the input.
  • In-place algorithms: O(1) space (only a constant amount of space is used).

3. Measuring Time in C:

You can measure the runtime of a program using the clock() function from time.h.

#include <stdio.h>
#include <time.h>

int main() {
    clock_t start, end;
    double cpu_time_used;

    start = clock();  // Start time

    // Your code here

    end = clock();  // End time
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("Time taken: %f seconds\\\\n", cpu_time_used);
    return 0;
}

• clock() returns the number of clock ticks since the program started.
• CLOCKS_PER_SEC is the number of clock ticks per second, used to convert the result into seconds.

4. Optimizing C Code:

• Avoid unnecessary loops: Use efficient algorithms.
• Reduce function calls: Minimize overhead by inlining functions.
• Efficient memory allocation: Use malloc() wisely, especially in large data sets.
• Data Structures: Use appropriate data structures to reduce time complexity (e.g., hash tables for O(1) lookups).