Time complexity of several methods of reversing a domain name string

Question

Note: I'm aware of this existing post which is similar. However, it does not address all my questions sufficiently.

---

I have the following three functions, all of which do the same thing: reverse a domain name string.

std::string reverse_domain(const std::string& s) {
    std::stringstream ss(s);
    std::string segment;
    std::vector<std::string> breakList;

    while (std::getline(ss, segment, '.')) {
        breakList.push_back(segment);
    }

    std::string result;

    auto size = breakList.size();

    for (int i = size - 1; i >= 0; --i) {
        result += breakList[i];

        if (i != size - 1) {
            result += ".";
        }
    }

    return result;
}

std::string reverse_domain2(const std::string& s) {
    std::string result;
    auto index = 0;

    for (const auto& c : s) {
        if (c == '.') {
            index = 0;
            result.insert(result.begin() + index, '.');
            continue;
        }

        result.insert(result.begin() + index, c);
        index++;
    }

    return result;
}

std::string reverse_domain3(std::string& copy) {
    std::reverse(copy.begin(), copy.end());
    auto start = 0;

    auto size = copy.size();

    for (auto i = 0; i <= size; i++) {
        if (copy[i] != '.' && i != size) continue;

        std::reverse(copy.begin() + start, copy.begin() + i);
        start = i + 1;
    }

    return copy;
}

My question is, what is the time complexity of all of these?

My educated guesses are:

• For reverse_domain: \$O(n) + O(n^2) + ?\$. The reasoning behind this is that I assume the getline loop is \$O(n)\$, and I assume appending to a string is \$O(n)\$, hence why I assume the for loop is \$O(n^2)\$. The last remaining piece is actually creating the string stream, hence the ? I have.

• For reverse_domain_2: \$O(n^2)\$. The reasoning behind this is that insert is linear time, and so the whole for loop would just be \$O(n^2)\$.

• For reverse_domain_3: \$O(n) + O(n^2)\$. The reasoning behind this is that reversal is linear time. And in the for loop, there's another reversal, hence \$O(n^2)\$. However, since its only reversing a piece of the string, I'm not too sure.

Are all these assumptions and time complexities correct?

I timed the performance of each of these methods on a multivariate plot, where the x axis is the length of the string, the y axis is the number of "." characters, and the z axis is the duration.

As you can see, reverse_domain is by far the slowest, and the other two are similar, with reverse_domain_3 being the fastest. However, I'm not exactly too sure why this is. I'm also not sure how to (or if I should) express the time complexity in terms of just the string length, or the length as well as the number of "." characters?

Thanks for any explanation(s).

Answer 1

reverse_domain()

This one has the largest extra space requirements, due to us creating a vector holding copies of all the components. It could be more efficient if the vector held string-view objects instead.

We could ensure that result doesn't need to reallocate if we reserve enough space - we know that it will be exactly the same size as the input string, because we're just rearranging the characters:

result.reserve(s.size())

We have a bug when we use int i to index the vector. Its size is a std::size_t, which has a different signedness and range to int. We can avoid the index variable altogether, though:

const char* sep = "";
for (const auto& component: std::views::reverse(breakList)) {
    result += sep;
    result += component;
    sep = ".";
}

Runtime should scale as O(n) - appending to a string that has enough capacity should be linear in the quantity being appended, and independent on the string's length (unlike std::strcat(), which needs to examine the whole string to find the end).

reverse_domain2()

We don't need to force the caller to pass a std::string here - we could accept a std::string_view instead.

This function has the same problem of not reserving result capacity.

The type of index is deduced from 0 as int, but we need a std::size_t - it's better to be specific here. Alternatively, and more simply, we can use an iterator into the result string (once we've made sure it won't need to reallocate):

auto it = result.begin();

The implementation of this one doesn't require any extra storage beyond what's needed for the result, but the insert() operation is costly because it involves moving the existing string data to make room. As you state, that makes this version scale as O(n²).

reverse_domain3()

This is problematic, because of the misleadingly-named argument copy, which is a reference. We ought to accept std::string by value rather than by reference; if callers no longer need the original, they can use std::move() to make the copy cheaper.

Again, we use the wrong types for start and size, and for the loop iterator i. All these should be std::size_t.

Instead of looping over each character, we can offload that to our library, using std::find() or std::string::find() to locate each '.' in the string.

The asymptotic complexity here is linear, O(n), because each character is affected exactly twice by std::reverse(). And like reverse_domain2, we use no extra storage (and can re-use the caller's storage if the argument is move-constructed).