How to calculate the time complexity of the Manacher's algorithm?


  • 0
    C

    I learned that Manacher's algorithm could solve the problem with O(n). Here is the link with code from Wikipedia: https://en.wikipedia.org/wiki/Longest_palindromic_substring#Implementation

    I'm confused about how to calculate the time complexity of the algorithm. Because it has two loops, the first is used to loop each item in the array, the second is used to expand around the center for each item, so my first guess is O(n^2). Somebody says that the total steps of the second loop is n, if this is true, then the time complexity is definitely O(n), but why is the total steps of the second loop is n?

    Any help appreciated.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.