How is time complexity different?

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?

Replay

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 0.008178000 seconds wall clock time.
C02QT2UBFVH6-lm:~ gsamaras$ pico main.c
C02QT2UBFVH6-lm:~ gsamaras$ gcc -Wall store.c
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out
That took 0.002047000 seconds wall clock time.

but what happens if

In the first example, assuming i 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 N2 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(N2).

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

They are different but almost the same because when you come to time complexity for example your first code contains one loop so that loop can repeat n times but the second code the statement appears one time and the loop n times so mathematically n+1 times that's the difference n and n+1 , but still we assume it as n goes to infinity so we always take the greatest power which is n , you can say as n goes to infinity 1 doesn't matter , both gives you almost the same result .

in fact the second method would use more time and memory than the first one. because the first method has less commands to be executed and less number of variables.

Category: c# Time: 2016-07-31 Views: 12

Related post

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development

search

Front-end development

Database

development tools

Open Platform

Javascript development

.NET development

cloud computing

server

Copyright (C) avrocks.com, All Rights Reserved.

processed in 0.135 (s). 12 q(s)