6

I'm looking at some online algorithm solutions for coding interviews, and I don't understand why this algorithm is claimed to be O(n^3).

Caveat: I understand that big-Oh notation is abused in industry, and when I refer to O(n), I'm using that notation to mean the upper bound of an algorithms runtime as is common outside of academia in most places.

Finding the longest palindromic substring. A simple solution might be:

bool isPalindrome(std::string s) {
  if (s.length() <= 1) {
    return true;
  }

  if (s[0] == s[s.length() - 1]) {
    return isPalindrome(s.substr(1, s.length() - 2));
  } else {
    return false;
  }
}

std::string longestPalindrome(std::string s) {
  std::string max_pal = "";
  for (size_t i = 0; i < s.length(); ++i) {
    for (size_t len = 1; len <= s.length() - i; ++len) {
      std::string sub = s.substr(i,len);
      if (isPalindrome(sub)) {
        if (max_pal.size() < sub.size()) max_pal = sub;
      }
    }
  }
  return max_pal;
}

Isn't this algorithm O(n^2)? Very simply, it takes O(n^2) time to generate all substrings, and O(n) time to determine if it's a palindrome. Where n is the number of characters in the initial string.

Improve this question
3
  • I wonder if it counting creating substrings as part of the complexity. Commented Nov 30, 2017 at 22:38
  • it takes O(n^2) time to generate all substrings, and O(n) to check each one Commented Nov 30, 2017 at 22:43
  • I know this wasn't the question, but here's a quick idea for an O(n^2) algorithm, for completeness' sake: There is only a linear number of possible "center points", and it takes at most a linear amount of time to count the length of each candidate by expanding it from the middle. There are palin. of even and odd length though, e.g. ABBA vs. BOB. For the former, we pick a center that is "between" two characters. Probably best to also start with a center point in the middle of the string. For inputs that contain the same character many times, this gets complexity down to O(n). Commented Dec 1, 2017 at 20:19

4 Answers 4

Reset to default
8

Isn't this algorithm O(n^2)? Very simply, it takes O(n^2) time to generate all substrings, and O(n) time to determine if it's a palindrome.

What you are describing is exactly O(n^3), because for each substring, you are doing an operation which costs O(n), so total number of operations is O(n^2 * C*n), which is O(n^3)

However, the code described is actually O(n^4), isPalindrome() is O(n^2):

  • You are creating O(n) substrings, of sizes: 1 + 3 + 5 + ... + n-2, which is O(n^2) total time.
  • Doing this O(n^2) times in longestPalindrome() totals to O(n^4).

(This assumes O(n) substr() complexity. It's not defined - but it's usually the case)

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

why is isPalindrome O(n^2)? Doesn't it check each character of the string exactly once?
@JohnDoe Since string::substr() is O(n), and you are doing it recursively along the way O(n) times. Total size of substrings created is 1 + 3 + 5 + ... + n-2, which is O(n^2).
Captain Obvious here… In C++17, a simple efficiency fix would be to change the parameter type of isPalindrome to std::string_view, whose substr has constant complexity. I'm pretty sure the whole problem could be solved with a O(n^2) worst case algorithm, though…
1

You are almost right, it takes O(n^2) and O(n) operations to generate the strings and check them. Thus, you need O(n^2) (amount of strings) times O(n) checks. Since n^2 * n = n^3, the total run time is in O(n^3).

Improve this answer

Comments

1

O(n^2) (substring turns out to be O(n) itself) is executed inside double loop (O(n^2)). That gives us O(n^4).

Improve this answer

4 Comments

That implementaiton is actually O(n^4).
Waaat? How? String.substring is O(1), how you've got O(n^4)?
From cplusplus.com Complexity: Unspecified, but generally linear in the length of the returned object. I am pretty sure in C++11 it must be linear, since COW is no longer a thing, but I am not going to commit on that.
Thanks for clarification, I've been sure that it reuses somehow underlying array.
0

Actually this'd be even O(N^4), because of the barbarity of the implementation.

isPalindrome is implemented in such a way, that for every recursive invocation it allocates a new string, which is essentially the source string with first and last chars removed. So every such a call is already O(n).

Improve this answer

1 Comment

I will have you know, sir, that I know some very talented barbarians. No one executes a divide and conquer algorithm like my old friend Tuborg the Barbarian. Assuming he's sober, that is. Drinks a lot.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.