Complexity of foo algorithm..?

I'm not really a CS person, but if N = strlen(A), won't the very first run-through of the for loop take theta(N) time? Overall it would be either theta(N) or theta(N log N). (Avoiding n since it is a variable name.)