What is the time complexity of the following program?

Question

#include <stdio.h>

void partition(int a[],int p,int r)
{

    int q;
    if(p<r)
    {
        q=quicksort(a,p,r);
        partition(a,p,q-1);
        partition(a,q+1,r);
    }
}

int quicksort(int a[],int p,int r)

{

    int pivot=p;
    int f=p,temp;
    int l=r;

    while(f<l)
    {
        while(a[f]<=a[pivot])
        f++;
        while(a[l]>a[pivot])
        l--;
        if(f<l)
        {
            temp=a[f];
            a[f]=a[l];
            a[l]=temp;
        }
    }
    temp=a[pivot];
    a[pivot]=a[l];
    a[l]=temp;
    return l;
}

int main(void)

{

    // your code goes here
    int n;
    scanf("%d",&n);
    int a[n];
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    partition(a,0,n-1);
    for(i=0;i<n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

This is an algorithm for quicksort my question is whether it takes more time complexity than O(nlogn).

my question is finding the time complexity of th given code but not of the quicksort? — Varun Teja, May 17 '15 at 11:13
@gaborous [1]: (http://geeksquiz.com/quick-sort/) does the code in this link and my code have the same time complexity — Varun Teja, May 17 '15 at 11:34
@VarunTeja: I'd say yes but it depends on 1- your inputs, 2- your implementation. I didn't try your code, but you can use the approach suggested by user3704217 to empirically test your implementation given some example inputs that you think are representative of the input that will be given by your users. If the mean time is nlogn, you're good to go! — gaborous, May 17 '15 at 18:33

score 0 · Answer 1 · answered May 17 '15 at 11:46

You can use clock() function to calculate the time taken by your code to execute.

The C library function clock_t clock(void) returns the number of clock ticks elapsed since the program was launched. To get the number of seconds used by the CPU, you will need to divide by CLOCKS_PER_SEC.

On a 32 bit system where CLOCKS_PER_SEC equals 1000000 this function will return the same value approximately every 72 minutes.

Sample Code:

#include <time.h>
int main()
{
    clock_t begin, end;

    begin = clock();

    //your code here

    end = clock();

    printf("Elapsed: %f seconds\n", (double)(toc - tic) / CLOCKS_PER_SEC);

    return 0;
}

To empirically measure the time complexity of your program, you need more than one data point. Run your program for multiple values of n, then make a graph of n vs. time. And See if it similar to nlogn graph or not.

What is the time complexity of the following program?

1 Answers1