0 votes 0 votes $O(n^k)$ is complexity of the best method that finds longest Palindrome Substring in a word. For example, in the word "Atatb", the longest palindrome string is "tat". Then, the value of $10^*K$ is __________. Algorithms tbb-algorithms-2 numerical-answers + – Bikram asked May 26, 2017 edited Aug 20, 2019 by Counsellor Bikram 581 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 1 votes 1 votes applying dynamic programming we get the the complexity as O(n2) Bikram answered May 26, 2017 selected Aug 5, 2019 by Bikram Bikram comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments akankshaR commented Dec 11, 2017 reply Follow Share it can be done in O(n) time also...why O(n2)??? 0 votes 0 votes I_am_winner commented Aug 10, 2018 reply Follow Share answer is not clear to understand ,please elaborate more sir 0 votes 0 votes Sambhrant Maurya commented Aug 5, 2019 reply Follow Share Yes Manacher's algo can do it in linear time. https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/ 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes O(nk) is complexity of the best method that finds longest Palindrome Substring in a word. So I think there is bit typo it supposed to be O($n^k$). Which is complexity of the longest palindrome sequence. If you have covered dynamic programming in algo, you must have read that complexity for palindrome sequence is O($n^2$). So k = 2 here. So the value of (10 * k) will be = 20. Ref for longest palindrome sub-sequence dp : https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/ logan1x answered Dec 1, 2019 logan1x comment Share Follow See all 2 Comments See all 2 2 Comments reply commenter commenter commented Dec 5, 2019 reply Follow Share But it can also be done in linear time. check comments of previous answeer. 0 votes 0 votes logan1x commented Dec 6, 2019 reply Follow Share Looks like you are right. Let's wait for @Bikram to explain or do correction in question. 0 votes 0 votes Please log in or register to add a comment.