can anyone tell me what is the time complexity of the below c++ function

Question

void swapminmax(int a[],int size){ //uses half the no of iteration to find min- max
int min,max= a[0];
int i;

for(i=0;i<=(size/2);i++){
    if(a[i]>a[size-i-1]){
        if(max < a[i]) max= a[i];
    }
    if (a[size-i-1]>a[1]) {
            if(max<a[size-i-1]) max = a[size-i-1];
        }
    if(a[i]<a[size-i-1]){
        if(min > a[i]) min = a[i];
    }
    else{
        if(min >a[size-i-1]) min = a[size-i-1];
    }
    }

    cout<<"min element: "<<min<<endl;
    cout<<"max element : "<<max<<endl;
}

Answer 1

The time complexity is O(N/2) but that is the same thing as 0(N)/2 which is the same thing as O(N).

The homework you want us to do for you ;) is trying to get you to understand that for time complexity k O(N) = O(N) whatever the value of k (the constant term). The idea is to think about what happens when N gets very very VERY big - then it really doesn't matter if that constant k (called a speedup factor) is big or small, what matters is the function N.

Try this exercise. Plot values of 0.1 * N for N between 0 and 200. Now plot values for 10 * log (N) for N between 0 and 100. At first 0.1 * N is smaller because the constant is small whereas the constant for 10 * log(N) is 100 times greater. As N grows bigger though it is the shape of the curve not the constant factor that is most important. At N = 100 the O(N) algorithm overtakes the O(log N) algorithm.

The lesson - however much you tinker with your code to make it 'efficient' by reducing the constant term e.g. writing in assembler instead of a script language, the algorithm and its time complexity function will always win out in the end.

Answer 2

O(N) with N=size, so it is linear to the size of your array (const factors are ignored when looking at run time complexity). Your loop condition depends only on i and size and none of them is modified in the loops body. There are no complex operations inside the loops body depending on the size.