# one for loop wraps 2 indexof method, what is the time efficiency?

I'm confused about how to know the time / space efficiency.

1. If there is an array whose size is n, do a for loop on this array, so that time efficiency should be O(n) = n, where n is array size. then if I have two indexof methods in the loop, indexOf and lastIndexOf, should the O(n) become n*(2n)? because each of the indexof methods has the time efficiency of n as well just like a for loop?

2. how to know the space efficiency of this method?

char firstNotRepeatingCharacter(String s) {

char[] str = s.toCharArray();
// n
for (int i = 0; i < str.length; i++) {

char item = str[i];
// 2n
if(s.indexOf(item) == s.lastIndexOf(item)) return item;

}
// 2n2

return '_';
}

• (There is "depends". On a future system not only identifying function parameter&result tuples to cache, but "queries" to invest preprocessing for, too.) In space analysis, there is additional space as well as total: what is your take? Jun 11 '20 at 8:05

So the code above has time complexity $$\mathcal O(n^2)$$
The space complexity depends on indexof's space complexity. Assuming it was done with a for loop and a simple comparison, the space complexity would be $$\mathcal O(log(n))$$ - as the storing the array length $$n$$ required $$log(n)$$ bits, and therefore keeping in memory the index i will take at most that much space.