How to improve time complexity of this code?

Question

How can I improve the time complexity of this code??

 $s = "Name";
    for($i=0; $i<strlen($s); $i++) {

    //some code

    }

You do realize this for loop is the fastest of all iterating loops? — Sterling Archer, Oct 28 '14 at 18:47
Sorry, was thinking javascript. Still, a basic for loop is still very fast. You're performing microoptimizations at this point — Sterling Archer, Oct 28 '14 at 18:49
Unless you're modifying the length of `$s` inside the loop, then use `$lenS = strlen($s); for($i=0; $i<$lenS; $i++) { //some code }`; and as a further micro-optimisation use `++$i` rather than `$i++` — Mark Baker, Oct 28 '14 at 18:49
Without knowing the problem it's impossible to guess an algorithm. — Markus Malkusch, Oct 28 '14 at 18:50
But what is `// some code`? You're more likely to be able to find optimisations in that than you are in execution of the looping mechanism — Mark Baker, Oct 28 '14 at 18:51
@MarkBaker OP's code has a complexity of O(n). Why do you think your's is better in terms of time complexity? — Markus Malkusch, Oct 28 '14 at 18:52
@Markus - #1.... no overhead of calling the `strlen()` function in every iteration of the loop; #2 no need for a temporary variable at opcode level if you preincrement rather than postincrement (depends on version of PHP). Neither changes the time complexity of the algorithm, they simply generate more efficient opcode; but OP isn't showing any algorithm anyway — Mark Baker, Oct 28 '14 at 18:53
@MarkusMalkusch How can I optimize the for loop? Since I am using the function strlen() in for loop, would it affect the time complexity?? — user3206062, Oct 28 '14 at 19:23
@MarkBaker It was an interview question. I answered exactly what you did except for the pre and post-increment. — user3206062, Oct 28 '14 at 19:25

score 0 · Answer 1 · edited May 23 '17 at 12:05

0

It depends on PHP's implementation of Strings and strlen(). If it is O(n) (which it is in GNU's C strlen()) the complexity of OP's code would be O(n²). Moving the strlen() out of the loop would improve to O(n) in this case:

$length = strlen($s);
for($i=0; $i<$length; $i++) {

//some code

}

However if the complexity of strlen() is O(1) (e.g. C++), The code is in O(n) and you can't improve it any more.

I have to admit, that I'm not fluent in C/C++, but I guess the length is a simple attribute of a zend_string, i.e. PHP's strlen() is O(1):

ZEND_FUNCTION(strlen)
{
    zend_string *s;
    // [..]
    RETVAL_LONG(s->len);
}

edited May 23 '17 at 12:05

Community

1
1

answered Oct 28 '14 at 19:53

Markus Malkusch

7,738
2
38
67

You're right in that strlen() is O(1) in core PHP. Moving the call to strlen() out of the loop won't change the time complexity, only reduce the overhead of n function calls to a single function call is an implementation detail – Mark Baker Oct 28 '14 at 20:47

How to improve time complexity of this code?

1 Answers1