TopCoder problem "Substitute" - SRM 160 (Division II Level One)
Analysis

You've picked an interesting problem about which to ask about Big-O complexity.  The problem is, you're being sloppy about what you call "n".  This function has two inputs: a key of length 10 and a code of variable length.  Let's say that m is the length of key (which is 10) and n is the length of code.

The outer i loop executes n times.  For each of those, outer loops, the inner j loop executes m times.  For each inner loop, key.indexOf() — an O(m) operation — is called; then we might do s = s + x — an O(n) operation.  Finally, Integer.parseInt(s) is an operation that I would expect to be O(n).

The complexity, therefore, is O(n ∙ m (m + n) + n).  If we consider m to be constant, that simplifies to O(n2).

However, the "silliest" part of the code is s = s + x.  That O(n) operation could be O(1) if you had used a StringBuilder instead of repeated string concatenation.  With a StringBuilder, your function would become O(n).

Perspective

It's important to keep a sense of perspective, though.  Big-O complexity is useful for getting a feel for how well an algorithm scales to handle large input.  For example, it can help you estimate whether an algorithm that analyzes a million DNA bases will finish in seconds or hours.

On the other hand, Big-O analysis is nearly useless for predicting the performance of "small" problems like this one.  The challenge states that n is at most 9 — and in any case, a result larger than 9 digits would overflow an int.  It is very possible that an algorithm that Big-O analysis predicts will scale well could actually perform worse than a simpler algorithm that in theory should scale poorly.  For example, the time it takes to initialize an "efficient" data structure could exceed the time it takes to do a naïve String.indexOf() search.

Suggested solution

Building a string and then parsing it as an integer is inefficient.  Why not just compute the integer as you go?

public int getValue(String key, String code) {
    int value = 0;
    for (int i = 0; i &lt; code.length(); i++) {
        int pos = 1 + key.indexOf(code.charAt(i));
        if (pos == 10) {
            value *= 10;
        } else if (pos &gt; 0) {
            value = 10 * value + pos;
        }
    }
    return value;
}