timing.c

// Compara tiempo de búsqueda lineal O(n) vs binaria O(log n).
//
// Uso: ./timing  [tamaños por defecto: 1k, 10k, 100k, 1M]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

int linear_search(int *arr, int n, int target) {
    for (int i = 0; i < n; i++)
        if (arr[i] == target) return i;
    return -1;
}

int binary_search(int *arr, int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else                   hi = mid - 1;
    }
    return -1;
}

double elapsed_ns(struct timespec a, struct timespec b) {
    return (b.tv_sec - a.tv_sec) * 1e9 + (b.tv_nsec - a.tv_nsec);
}

int main(int argc, char *argv[]) {
    int sizes[] = {1000, 10000, 100000, 1000000};
    int nsizes  = sizeof sizes / sizeof sizes[0];
    int repeats = 10000;

    printf("%-10s | %-15s | %-15s | speedup\n", "n", "linear (ns)", "binary (ns)");
    printf("---------------------------------------------------------\n");

    for (int s = 0; s < nsizes; s++) {
        int n = sizes[s];
        int *arr = malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) arr[i] = i * 2;     // ordenado

        struct timespec t1, t2;
        long target = (n / 2) * 2;

        clock_gettime(CLOCK_MONOTONIC, &t1);
        for (int r = 0; r < repeats; r++) linear_search(arr, n, target);
        clock_gettime(CLOCK_MONOTONIC, &t2);
        double lin = elapsed_ns(t1, t2) / repeats;

        clock_gettime(CLOCK_MONOTONIC, &t1);
        for (int r = 0; r < repeats; r++) binary_search(arr, n, target);
        clock_gettime(CLOCK_MONOTONIC, &t2);
        double bin = elapsed_ns(t1, t2) / repeats;

        printf("%-10d | %-15.2f | %-15.2f | %.1fx\n", n, lin, bin, lin / bin);
        free(arr);
    }
    return 0;
}