mb_substr

PHPの実装を読んでないけど、実験結果とマルチバイト文字の性質からから推測。

asciiのみの文字列の時は1文字1byteを想定しているので、先頭からn文字目を参照する時は先頭からn byte目を参照すればいい。

でもmb_*で扱う文字列の場合、1文字が1〜6byteと可変(shift-jis及びeucは2byte、日本語UTF-8は3byte、全言語UTF-8ならら2〜6)なので、先頭からn文字目を参照する時に何byte先を参照したらいいか分からない。そのため先頭から1文字ずつ読んでいってn文字目を探す必要があり、nに比例した時間がかかってしまう。(asciiのみの場合はnが大きくても時間は変わらない)

以上より、substrの時はNに比例した時間になり、mb_substrの時は部分文字列の先頭の位置を探し出すのにNに比例する時間がかかり、それをさらにN回実行しているのでN^2に比例した時間になっているのだと思われます。