If I write some thing like this
for(int i = 0 ; i < strlen(s) ; i++)
will it be O(n^2) ?
Also please tell me where can I see codes of standard library of C (GCC) in Ubuntu.
If I write some thing like this
for(int i = 0 ; i < strlen(s) ; i++)
will it be O(n^2) ?
Also please tell me where can I see codes of standard library of C (GCC) in Ubuntu.
The complexity depends what the loop body does. It is, however, not a good idea to evaluate strlen(s) every iteration if you care about efficiency, unless the contents of s changes within the loop body. Try evaluating strlen(s) before the loop, once only.
You can download the source for various versions of gcc from somewhere on this site. Somewhere among those source distribution will be the source for libc (if I remember the name correctly), which is gnu's corresponding implementation of the C standard library.
I'm not exactly sure, but isn't your for loop actually O(n*i)?
Thanks
Wouldn't it just be directly proportional to the string length (linear)?
O(n)?
strlen(s) has O(n) run time, where n is the length of the string. strlen(s) is called n times, so yes, the loop is O(n^2). As grumpy said, you should call strlen(s) once before the loop.
EDIT: strlen could theoretically be implemented with O(1) run time, such as on a processor that can find the first 0 byte in constant time, but this is only theoretical. Assume strlen is O(n).
Last edited by christop; 06-08-2012 at 10:02 AM.
Of course, missed that.
Basically an O(n) nested in an O(n).
The reason "The complexity depends what the loop body does." is that the loop might say append characters onto the string s, or put a null-terminator earlier in the string, or it might have another loop inside this one etc.
Without anything special going on, it is as was originally guessed.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
Thank you all guys