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 '_';
  • $\begingroup$ (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? $\endgroup$
    – greybeard
    Jun 11 '20 at 8:05

Yes, you are correct. But time complexity we measure only in big-O notation.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.