understanding algorithmic complexity

Question

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.

Answer 1

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)

Answer 2

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).

Answer 3

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).