How is time complexity different?

Question

Does it save time if the value is stored first and then used?
For example;

while(i<strlen(s))
 //code

and

int n = strlen(s);
while(i<n)
 //code

Is the time complexity lower for the second method as the return value of the function is first stored and then used,thus avoiding calling the function every time it enters the loop?

Answer 1

In the first example, assuming i is initialized appropriately (to 0 probably) and is incremented in the loop body, you will count the number of characters in the string s each time around the loop, so if there are N characters in the string, you'll do N² comparisons (because strlen() compares each character in the string against '\0', and you'll do the explicit loop N times, and the loop inside strlen() N times each call), making the code O(N²).

In the second example, again assuming i is initialized and incremented in the loop body, you will count the number of characters once, so you'll do N comparisons, making the code O(N).

Whether the optimizer can safely optimize the calls to strlen() out of the loop control depends on what is in the body of the loop. If the compiler can see everything, or can determine that the called code cannot legitimately modify the string s, then it may be able to move the call to strlen() out of the loop control, effectively giving the O(N) performance of the second loop. OTOH, if the body of the loop calls a function and passes a non-const pointer to s to the function, then the compiler may not be able to assume that the string is unmodified and may have to call strlen() on each iteration.

Answer 2

A clever compiler will do the second for you. So don't worry about this and don't be a victim of premature optimization!

---

You want the second one, because the length has a fixed value and you will avoid the call of the function per loop.

---

But will the compiler be clever enough to do so? Only if you tell him too! See the examples below:

First, I am compiling without optimization flags:

C02QT2UBFVH6-lm:~ gsamaras$ gcc -Wall nostore.c
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out
That took 27.701602000 seconds wall clock time.
C02QT2UBFVH6-lm:~ gsamaras$ gcc -Wall store.c
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out
That took 12.100676000 seconds wall clock time.

but what happens if we use an optimization flag?

C02QT2UBFVH6-lm:~ gsamaras$ gcc -O3 -Wall nostore.c
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out
That took 0.004949000 seconds wall clock time.
C02QT2UBFVH6-lm:~ gsamaras$ gcc -O3 -Wall store.c
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out
That took 0.005283000 seconds wall clock time.

Compiler did it better than me! Compilers are not that dumb nowadays, as some people mistakenly think.

For timing I used the Nomimal Animal's approach from my Time measurements.

Here is the cod I executed:

char* str = "What's faster? What's a premature optimization? Am I a vi$
int i = INT_MAX;

// int n = strlen(str);
// while(n);
while(strlen(str)) {
    // do some random work so that you don't get 0 timing
    int a = 3;
    double pi = 3.14;
    a /= pi;
    a = a % (i + 1);
    // break when 'i' is 0
    if(!i)
        break;
    --i;
}

---

But are optimization flags that important in benchmarking? YES, check this question: Poor performance of stl list on vs2015 while deleting nodes which contain iterator to self's position in list