#include <stdio.h>   // Includes the standard input/output library
#include <time.h>    // Includes the library for time-related functions

int main() {
    clock_t start_time, end_time;  // Variables to store the start and end times
    double cpu_time_used;          // Variable to store the CPU time used

    // Record the start time
    start_time = clock();  // 'clock()' returns the number of clock ticks since the program started

    // Place your code to measure execution time here
    // For example, let's simulate some computation
    int sum = 0;  // Variable to store the sum
    for (int i = 1; i <= 1000000; ++i) {  // Loop from 1 to 1,000,000
        sum += i;  // Add the current value of 'i' to 'sum'
    }

    // Record the end time
    end_time = clock();  // 'clock()' returns the number of clock ticks since the program started

    // Calculate the CPU time used in seconds
    // 'end_time - start_time' gives the number of clock ticks taken by the code block
    // Dividing by 'CLOCKS_PER_SEC' converts the clock ticks to seconds
    cpu_time_used = ((double) (end_time - start_time)) / CLOCKS_PER_SEC;

    // Print the result of the computation and the CPU time used
    printf("Sum: %d\\n", sum);  // Print the calculated sum
    printf("CPU Time Used: %f seconds\\n", cpu_time_used);  // Print the CPU time used in seconds

    return 0;  // Return 0 to indicate successful program execution
}

#include <stdio.h>        // Includes the standard input/output library
#include <sys/time.h>     // Includes the library for time-related functions on the system
#include <time.h>         // Includes the libaray for time-related functions

int main(){
    struct timeval before;    // Declare a structure to hold the time before the computation
    gettimeofday(&before, NULL);  // Get the current time and store it in 'before'
    // Calculate the time in milliseconds
    long long before_millis = before.tv_sec * 1000LL + before.tv_usec / 1000;

    int sum = 0;  // Variable to store the sum
    // Loop to perform the computation
    for (int i = 0; i < 100000000; i++) {
        sum += i;  // Add the current value of 'i' to 'sum'
    }

    struct timeval after;    // Declare a structure to hold the time after the computation
    gettimeofday(&after, NULL);  // Get the current time and store it in 'after'
    // Calculate the time in milliseconds
    long long after_millis = after.tv_sec * 1000LL + after.tv_usec / 1000;

    // Print the difference in milliseconds, which is the time taken for the computation
    printf("%llu MS\\n", after_millis - before_millis);
    return 0;  // Return 0 to indicate successful program execution
}

Time complexity is a measure used to describe the efficiency of an algorithm in terms of the time it takes to run as a function of the size of its input. Understanding and being able to calculate time complexity is crucial for optimizing code and making informed decisions about algorithm choices. Here’s a comprehensive guide to calculating time complexity from an interview perspective:

Key Concepts

  1. Big O Notation: Big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows. It provides an upper bound on the time complexity, giving the worst-case scenario.
  2. Basic Operations: These are the fundamental steps of an algorithm (e.g., arithmetic operations, comparisons, and assignments). Time complexity is often derived by counting the number of basic operations.
  3. Input Size (n): The size of the input to the algorithm. It is often represented by n.
  4. Worst-Case, Best-Case, Average-Case:

Steps to Calculate Time Complexity

  1. Identify the Basic Operation: Determine the operation that contributes most significantly to the running time of the algorithm (e.g., comparisons in a sorting algorithm).
  2. Count the Basic Operations: Analyze how many times the basic operation is executed as a function of the input size n.
  3. Express in Big O Notation: Simplify the count to its dominant term and express it using Big O notation.

Common Time Complexities