For the heck of it, I wrote the same thing (I hope) in JavaScript:
(() => {
const str = "My Rob is a cool Robert! His name is Robert... ".repeat(13);
/* start time */
const startTime = new Date().getTime();
for (let i = 0; i < 100000; i++) {
const regEx = /Rob/ig;
const matches = str.matchAll(regEx);
const locations = [...matches].map(m => m.index);
}
const elapsedTime = new Date().getTime() - startTime;
console.log(elapsedTime);
})()
Result is 3205 ms for 100,000 iterations, so about 0.03 ms per iteration when run in Script Editor. On the command line (osascript ...), it runs in a little less time: 2800 ms, i.e. 0.028ms per iteration. I don’t know what the Script Geek timings are in.
I tried the code with a considerably longer string, containing 4096 matches. Then it took about 34 ms per iteration (in Script Editor). So, the run-time behavior is > O(n).