How do I analyze the running time of an algorithm in C?

Question

I'm supposed to write an algorithm and analyze and compare its running times for best and worst case scenarios. The assignment reads

Choose an algorithm and implement it in C. Then analyze it in at least one of the criterias of running time, memory need etc. This analysis must be visualized inside your code with the data you automatically get from your code. For example if you're going to analyze your code's running time, you should edit your code in a way that works iteratively with different sized datas and shows its running time with a simple bar diagram in every run.

I'm pretty new at this stuff so I couldn't figure out how. Is there a function to use or a built in tool in IDEs?

This is my code. It's a simple brick sort algorithm.

#include <stdio.h>

int n, i, a[100], temp, isSorted;

int brickSort(int a[], int n)
{
    isSorted=0;
    
    while(isSorted==0)
    {
        isSorted=1;
        
        for(i=0; i<=n-2; i=i+2)
        {
            if(a[i]>a[i+1])
            {
                temp=a[i];
                a[i]=a[i+1];
                a[i+1]=temp;
                isSorted=0;
            }
        }
        
        for(i=1; i<=n-2; i=i+2)
        {
            if(a[i]>a[i+1])
            {
                temp=a[i];
                a[i]=a[i+1];
                a[i+1]=temp;
                isSorted=0;
            }
        }
    }
    
    for(i=0; i<n; i++)
    {
        printf("%d ", a[i]);
    }
}

int main()
{
    printf("Enter the amount of numbers ");
    scanf("%d", &n);
    
    for(i=0; i<n; i++)
    {
        printf("Enter number ");
        scanf("%d", &a[i]);
    }
    
    return brickSort(a, n);

    return 0;
}

Answer 1

When we say run time, it means true data, not idealism.

Let us take brick sort on linux as example.

root@sz:~/brick$ ./a.out 
3 5 1 6 9 7 8 0 11 12 
brick sort took 0.007000 ms to execute 100
brick sort took 2760 KB to execute 100
0 1 3 5 6 7 8 9 11 12 
root@sz:~/brick$ cat a.c
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>  
void swap(int *a, int *b)
{
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

void printArray(int a[], int count)
{
    int i;
    for(i = 0; i < count; i++)
        printf("%d ",a[i]);
    printf("\n");
}

void Odd_even_sort(int a[], int size)  
{
    bool sorted = false;
    while(!sorted)
    {
        sorted = true;
        for(int i = 1; i < size - 1; i += 2)
        {
            if(a[i] > a[i + 1])
            {
                swap(&a[i], &a[i + 1]);
                sorted = false;
            }
        }
        for(int i = 0; i < size - 1; i += 2)
        {
            if(a[i] > a[i + 1])
            {
                swap(&a[i], &a[i+1]);
                sorted = false;
            }
        }
    }
}

#include <time.h>
#include <sys/time.h>
#include <sys/resource.h>
#define CNT 100

int main(int argc, char *argv[])   
{
    int a[] = {3, 5, 1, 6, 9, 7, 8, 0, 11, 12};
    int n = sizeof(a) / sizeof(*a);
    printArray(a, n);
    clock_t t;
    t = clock();
    int count = CNT;
    while (count--) {
        Odd_even_sort(a, n);
    }
    t = clock() - t;
    double time_taken = ((double)t)/CLOCKS_PER_SEC*1000; // in miliseconds
    count = CNT;
    printf("brick sort took %f ms to execute %d\n", time_taken, count);
    struct rusage r_usage;
    getrusage(RUSAGE_SELF,&r_usage);
    printf("brick sort took %ld KB to execute %d\n", r_usage.ru_maxrss, count);
    printArray(a, n);
    return 0;
}

The algorithm ran 100 rounds and get time and memory usage from GNU C get api functions.

We can change the input array to find out the real worst case and best case, which result in below table.

--------------------------------------------------------
| Array               | Time (ms) | Space (MB) | Round |
--------------------------------------------------------
| 3 3 3 3 3 3 3 3 3 3 | 0.004000  | 2.76       | 100   |
--------------------------------------------------------
| 3 3 3 3 3 3 3 3 3 3 | 0.043000  | 2.76       | 1000  |
--------------------------------------------------------
| 3 3 3 3 3           | 0.020000  | 2.76       | 1000  |
--------------------------------------------------------
| 3 5 1 6 8           | 0.015000  | 2.76       | 1000  |
--------------------------------------------------------
| 4 5 6 7 8           | 0.023000  | 2.76       | 1000  |
--------------------------------------------------------

So space complexity follows O(1) yet time hard to say, in fact results differ (due to mordern OS self-optimization) in different runs even with same array...

Answer 2

I'm pretty new at this stuff so I couldn't figure out how. Is there a function to use or a built in tool in IDEs?

For your question, there isn't any function or built in tool in IDEs to use for calculating the time complexities. I would suggest to use pen & paper for calculating as a beginner.

As for your brickSortfunction, write down the number of times that is to be executed in each line (you may write those in terms on n (and sometimes constant, i.e 1)). For example, your isSorted initialization will be running for constant (1) time. The while loop is gonna run for everytime the isSorted is 0, write the number of times. The first for loop is gonna run for n/2 times and same goes for second. Analyze each line in the for loop. Possibly understand how many times each line is gonna be running for each condition, initialization, loops and then adding it will give you the running time in terms of n after elimination of constants (in your function - O(n)). If you have only constants, it is running in constant time, which is the best possible running time for any function.

Running times for best and worst case scenarios:

You may want to analyze each line of the code when the given array is already sorted, reversely sorted and partially sorted. Analyze the running time when the array is already sorted, how many times your lines will be executed, it will give you the best case. And for the reversely sorted, and partially, it will give you worst case and average case respectively.

Answer 3

Is there a function to use or a built in tool in IDEs?

Not that I'm aware of. Human brain required. :)

However, here are some tentatively-educational pointers (in addition to the very helpful comment of Eric Postpischil):

Running Time

To estimate running time you will likely start by using asymptotic notation - this is the *summarized estimate+ of how much the algorithm will take in best/worst/average cases.

• Worst case scenario: Big O Notation
• Best case scenario: Omega Notation
• Average case scenario: Theta Notation

https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Time_complexity

If you're just starting, you're probably being asked the best/worst cases.

Quick side note for motivation: why would this be useful in real life? There's plenty of applications that require sorting, such as get the top chess players from Russia, or sort chess Grandmasters by their age. If your website gets thousands of views per second, doing these things fast and efficiently will result in a better experience for your users, as well as reduced costs for you.

It's good to start analysing what your algorithm is doing. For asymptotic analysis, the most important parts are loops (or function calls that themselves may contain loops/function calls, without forgetting about recursive calls…).

- Q1: What is your algorithm doing?

The for loops each appear to be going through N/2 elements (for an array of 10 elements, each loop runs 5 times). In Big-O notation, this would be O(N/2), but we don't care about constants, so it's correct to state O(N).

Their combined time complexity is O(N) + O(N) = 2*O(N) = O(N) (because, again, constants disappear). So, the time complexity of an iteration of the outer loop is O(N).

This leaves the outer loop - how many times will it run? This will be the main problem, and will depend on the array. The time complexity of your algorithm will be the number of times the outer loop runs multiplied by the time complexity of each of those iterations.

- Q2: How many times will the outer loop run?

For example, if the array is already sorted (e.g. [1, 2, 3]), then the outer loop will run just once. This is the best case scenario: Ω(N).

What is the worst possible array you can imagine? That's where human ingenuity comes to play. :-)

- Q3: Average case scenario?

Not sure if this still part of the scope of your assignment. It's more tricky, as average may vary from application to application. Usually at a learning level it's OK-ish to assume a uniform distribution (i.e. any input is as likely as any other).

Then you start to play with probabilities. What's the probability of getting an array that does 1 iteration of the outer loop? What about 2? What about N?

Space Complexity

This is a similar analysis, but instead of looking at the number of instructions, usually we look at the memory used (e.g. mallocs within loops).

This is an in-place algorithm, so not the most interesting… :)

Answer 4

How do I analyze the running time of an algorithm in C?

I don't know how you do it.

How I do it is to try to estimate the total number of potential cache misses and the total number of potential branch mis-predictions. The theory is that modern CPUs can do multiple instructions per cycle, but a cache miss or branch mis-prediction costs tens or hundreds of cycles, so typically the cost of most normal instructions is negligible/ignorable and only cache misses and branch mis-predictions have a large enough performance impact to worry about.

For your code; for branch mis-predictions; it's likely that the if(a[i]>a[i+1]) branches will quickly become "predicted not taken" by the CPU's branch predictor after the first iteration of the outer while(isSorted==0) loop. It's reasonable (as a "not accurate but close enough" estimate) to say that the number of branch mis-predictions will depend on how sorted the original array was (e.g. the array "1, 3, 7, 12, 14" is already sorted and won't have many branch mis-predictions, but "14, 12, 7, 3, 1" is very unsorted and will cause a lot more branch mis-predictions). The while(isSorted==0) branch itself can be ignored (likely mis-predicted once, which isn't enough to worry about).

For cache misses there's 2 cases - either the whole array fits in the cache (and the total potential cache misses is directly related to the size of the array alone); or the array is too big to fit in the cache so it's constantly thrashing the daylights out of the cache (and the total potential cache misses is related to the size of the array multiplied by however many times the while(isSorted==0) outer loop executes). The number of times the while(isSorted==0) outer loop executes depends on how well sorted the original array was.

However...

Your question may not be the question you wanted to ask; and you may have wanted to ask "How does my uni/course want me to analyze the running time of an algorithm?". If your uni/course introduced you to "big O notation" (see https://en.wikipedia.org/wiki/Big_O_notation ) recently, then it's likely that your uni/course wants you to use "big O notation" to find a meaningless pseudo-estimate that has almost no correlation with performance at all (in an "O(n*n) is faster than O(n) for all practical values of n" way).