Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Complexity of comparison operators [duplicate]

Tags:

Why does the y[i] < x[i] function take twice the time when array x is always higher in value than y (for ex 1<x<2, and 0<y<1). In addition, when comparing 0.5<x<1.5, and 0<y<1, the execution time is about 1.5x the case where 0<x<1, and 0<y<1. This is assuming that both x and y are long arrays.

I add the code for you to try and get what I mean. you can offset the array x by increasing and decreasing the variable "offset (try offset =1 and offset =0); The code will store the execution time for the loops in the file Beta.

code is :

#include <iostream>
#include <array>
#include <time.h>
#include <math.h>
using namespace std;
#define MAX(x,y) ((x) > (y) ? (x) : (y))

int main()
{
ofstream myfile_Beta;
myfile_Beta.open ("Beta.txt");
clock_t begin_time = clock();
clock_t total_time;
srand (time(NULL));

double offset =0.0;

int m=0;
for(int k=0;k<10000;k++)
    {
    m=1;
    double M[75720],x[75720],y[75720];

    for (int i=0;i<75720;i++)
    {

        x[i]=+(rand()%1024)/1024.0* 1.0 + offset ;
        y[i]=+(rand()%1024)/1024.0* 1.0 + 0.00; 
    }
    begin_time = clock();
    for (int j=0;j<75720;j++)
    {
        M[j]=MAX(x[j],y[j]);
    }   
    total_time =clock () - begin_time;
    myfile_Beta <<float( total_time  )<<" "<<endl;
}
myfile_Beta.close ();
}
like image 648
user304584 Avatar asked Mar 25 '15 15:03

user304584


People also ask

What is the time complexity of comparison?

The time complexity, measured in the number of comparisons, then becomes T(n) = n - 1. In general, an elementary operation must have two properties: There can't be any other operations that are performed more frequently as the size of the input grows.

What does === comparison operator do?

The strict equality operator ( === ) checks whether its two operands are equal, returning a Boolean result. Unlike the equality operator, the strict equality operator always considers operands of different types to be different.

Is comparison a constant time operation?

Comparison and substitution operations are a constant factor because their execution time doesn't depend on a size of the input. Their execution time takes time but, again, it's independent from the input size.


1 Answers

One explanation is that there are less jumps if the first condition applies,

The second explanation regards branch predication, basically, where it could 'guess' the '<' result and apply the next code regardless of the result, and muck it on failure, so when you have the same condition happening relatively a lot, the compiler can guess it correctly more often. You can read more about it here: http://en.wikipedia.org/wiki/Branch_predication

like image 195
Alon Avatar answered Sep 19 '22 06:09

Alon