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.