CODEWITHSUNDEEP
c++
user466534
user466534

Reputation:

question about algorithm complexity

i have tried implement two methods recursive and dynamic method and both took 0 second it means that no one is better in my computer or something is wrong in code? here is these methods

1// recursive

#include <stdio.h>
#include <time.h>
#include <iostream>
using std::cout;
void print(int  n){

    if (n<0)  return ;
    cout<<n<<" ";

    print(n-1);

}
int main(){
    int n=10;
    time_t  start,end;
    double dif;
    time(&start);
    print(n);
    time(&end);
    dif=difftime(end,start);
    printf("it took you %.21f seconds ",dif);

     return 0;
}

2.second method

#include <iostream>
#include <stdio.h>
#include <time.h>
using namespace std;
void print (int n){
    if (n<0) return ;
     while (n>=0){
         cout<<n--<<endl;
     }



}
int main(){
    int n=10;
    double dif;
    time_t start,end;
    time(&start);

    print(n);
    time(&end);
    dif=difftime(end,start);
    printf("it took you %.21f seconds",dif);

 return 0;

}

Upvotes: 1

Views: 291

Answers (5)

cape1232
cape1232

Reputation: 1009

Also gettimeofday() returns time in microseconds.

Upvotes: 0

Peter G.
Peter G.

Reputation: 15114

For a thorough performance measurement you have to repeat the tested function, preferably with repeatably randomized inputs so often that you achieve a running time that is withing your measurement resolution. Then, repeat the measurements a couple of times, remove the outliers and average over the remaining values. Now you should have solid numbers to look at.

Upvotes: 0

Martin B
Martin B

Reputation: 24140

The time taken by both functions is smaller than the timer resolution, which is why you're measuring 0 seconds.

Asymptotically, both functions have a time complexity of O(n).

Upvotes: 2

Aoi Karasu
Aoi Karasu

Reputation: 3825

When testing, you need to loop your function 100.000 times or so and measure the whole loop time. Then you will be able to see some reliable results.

Upvotes: 1

ereOn
ereOn

Reputation: 55726

A second clock resolution is not suitable for measuring such fast operations.

I suggest you execute your code many times (something like 1 million times; use a for loop for this), estimate the overall time and then compute an average value.

This way you'll get more reliable results.

Just a quick note: I see you use cout in your functions. This is a bad idea: cout and usually most I/O operations are slow regarding to other operations. It is likely that your functions will spend most of their time to print the value, instead of computing it.

Upvotes: 7

Related Questions