How to check the efficiency of these 2 functions in C++?

Overall, the responses to date deal with the measurement of efficiency in practical terms.

I will give an answer in theoretical terms, since you ask two questions: how to determine the equations of complexity and whether there is another method.

To answer the first question, first of all I recommend an introductory book of algorithms that teaches Big-O notation.

The books I recommend are:

• algorithms: theory and practice - Known internationally, particularly I only had access to the English version .
• Algorithms Unlocked - I did not have access, but it is well recommended for being a less long version of the previous book. Written by the same renowned author.
• Schaum's Outline of Discrete Mathematics - I like this book to be very direct, more appropriate for those who are not beginners perhaps. Not exactly focused on algorithms, it covers several important areas of computer science (particularly I feel I'm even more accessible than "algorithms: theory and practice" at certain points when it comes to algorithms).

I will reduce the analysis in kids, not strictly, without involving loop invariants , etc.

First the easiest to analyze, case 2.

This case consists of only one loop that repeats an operation of complexity O(1). The amount of repetitions is directly proportional to the input value function. If the argument x is N, then the loop is repeated N times. Outside the loop, the function body only has other complexity operations O (1):

int Y(int x) { // O(1)
    int soma=0; // O(1)

          // O(1)   O(1)   O(1)
    for(  int i=0;  i<=x;  ++i  )
        soma+=i; // O(1)
    // O() do loop = O(x) == O(1) + x*O(1) + x*O(1) + x*O(1)

    return soma; // O(1)
}
// O() da função = O(x) == O(1) + O(1) + O(x) + O(1)

So this function has O(N) complexity in time. Note that this function performs its calculation with a fixed amount of local variables only, so it is O (1) in the space used (i.e. it does not need more memory depending on the input).

The first case is a recursive function, and the analysis of complexity becomes recursive too. There is a solid theory for this, but I will stick to one simplistic explanation.

Note that all operations in the function body except the recursive call itself are O(1). Recursive calls will occur until the termination condition is reached. Note that for an input x = N, N calls occurred. Given that in each call, other than the recursive call, O(1) operations are performed, then the time complexity of this function is also it's O (N).

The complexity in the space of this function differs from Case 2. Because it is a recursive function whose result needs to be aggregated as a sum at the end, it is not a function tail-recursive, and therefore it is not possible for the compiler to optimize its function using this technique.

Since tail-recursion is not possible, each recursive call must be stacked in the call stack a fixed number of data (arguments from the function, return address, etc.). That is, for N calls, Ndata stacks of a given size occurred, so the function is O(N) in the space it uses as well.

Answering the second question: Is there another method?

You have two solutions to the problem, one is O(N) in time and O(N) in space, one is O(N) in time and O(1) in space.

An alternative would be to look for a solution whose complexity does not depend on the input value, is it possible a solution O(1) in time and O(1) in space?

Note that:

• y = 1 + 2 + 3 ... + (x-2) + (x-1) + x
• y - x * x = (1 - x) + (2 - x) + (3 - x)... + [(x-2) - x] + [(x - 1) - x] + (x - x)
• - (y-x * x) = (x-1) + (x - 2) + (x - 3)... + 2 + 1 + 0
• x * x-y = 1 + 2... + (x - 3) + (x - 2) + (x - 1)
• x * x-y = y-x
• x * x + x = 2y
• y = x * (x + 1) / 2

Of this formula (a basic deduction of the sum of the elements of an arithmetic progression), it is possible to obtain the value of the sum from the input value with complexity O(1), that is, without loops.

Then the most efficient method would be:

int Z(int x) { // O(1)
    return (x * (x + 1)) / 2; // O(1)
}

(if you ever wondered in life where that would use PA and PG taught in school, there it is; -))

If you wanted to be even more efficient, with C++11 you could declare the function as constexpr.

constexpr int Z(int x) {
    return (x * (x + 1)) / 2;
}

Thus, most compilers that supports C++11 would do compile-time sum calculation, incurring no run-time calculation, when the passed argument is a constant. If the argument is not a constant (i.e. a runtime value), the function gets the same efficiency as a inline version.

Improving performance:

In g++ there is the -Ofast flag that makes several modifications during the build phase of your algorithm and, most of the time, it gets much more efficient!

I have already reduced executions that lasted 20 minutes to less than 1!

Here is an example:

G main main.cpp-the App.exe-Ofast

Take the test, calculate the runtime as the other answers suggest, and make your own conclusions!

No Windows

#include <stdio.h>
#include <windows.h>

int main() { 
    int i, j; 
    int inicio, final, tmili; 

    inicio = GetTickCount(); 

    /* Substitua o for a seguir pelo trecho de código 
       cujo tempo de execução deverá ser medido. */

    for (j = 0; j < 10; j ++) 
        for (i = 0; i < 1387634340; i ++); 
    final = GetTickCount();
    tmili = final - inicio; 

    printf("tempo decorrido: %d\n", tmili); 
    return 0; 
}}

No Linux

#include <stdio.h>
#include <sys/time.h>

int main() { 
    int i, j;
    struct timeval inicio, final;
    int tmili;

    gettimeofday(&inicio, NULL);

    /* Substitua o for a seguir pelo trecho de código 
       cujo tempo de execução deverá ser medido. */

    for (j = 0; j < 10; j ++) 
        for (i = 0; i < 1387634340; i ++); 
    gettimeofday(&final, NULL);
    tmili = (int) (1000 * (final.tv_sec - inicio.tv_sec) + (final.tv_usec - inicio.tv_usec) / 1000);

    printf("tempo decorrido: %d\n", tmili); 
    return 0; 
}

How to calculate efficiency I don't know but I can test it:

#include <stdio.h>
#include <time.h>
#include <cstdint>

#ifdef WIN32
#include <Windows.h>
#else
#include <sys/time.h>
#include <ctime>
#endif

/* Returns the amount of milliseconds elapsed since the UNIX epoch. Works on both
 * windows and linux. */

uint64_t get_time()
{
#ifdef _WIN32
 /* Windows */
 FILETIME ft;
 LARGE_INTEGER li;

 /* Get the amount of 100 nano seconds intervals elapsed since January 1, 1601 (UTC) and copy it
  * to a LARGE_INTEGER structure. */
 GetSystemTimeAsFileTime(&ft);
 li.LowPart = ft.dwLowDateTime;
 li.HighPart = ft.dwHighDateTime;

 uint64_t ret = li.QuadPart;
 ret -= 116444736000000000LL; /* Convert from file time to UNIX epoch time. */
 ret /= 10000; /* From 100 nano seconds (10^-7) to 1 millisecond (10^-3) intervals */

 return ret;
#else
 /* Linux */
 struct timeval tv;

 gettimeofday(&tv, NULL);

 uint64_t ret = tv.tv_usec;
 /* Convert from micro seconds (10^-6) to milliseconds (10^-3) */
 ret /= 1000;

 /* Adds the seconds (10^0) after converting them to milliseconds (10^-3) */
 ret += (tv.tv_sec * 1000);

 return ret;
#endif
}

int X(int x){
    if(x<=0)
        return 0;
    return(x + X(x-1));
}

int Y(int x){
    int soma=0;
    for(int i=0;i<=x;++i)
        soma+=i;
    return soma;
}

int main(void) {
    uint64_t startTime, endTime, timeElapsed;
    startTime = get_time();
    X(300000);
    endTime = get_time();
    timeElapsed = endTime - startTime;
    printf("Tempo decorrido: %d\n", timeElapsed);
    startTime = get_time();
    Y(300000);
    endTime = get_time();
    timeElapsed = endTime - startTime;
    printf("Tempo decorrido: %d\n", timeElapsed);

    return 0;
}

I put on GitHub for future reference.

I did one Test and the second was clearly much more efficient, at least 7 times faster. I couldn't post on any website online that would allow it to run properly. Where you ran can't share.

The measurement function was taken from this response in the OS.