edited by
581 views
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 __________.
edited by

2 Answers

Best answer
1 votes
1 votes

applying dynamic programming we get the  the complexity as O(n2)

selected by
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/

Answer:

Related questions

2 votes
2 votes
2 answers
2
Bikram asked May 26, 2017
343 views
Assume Dijkstra's Algorithm is used to find the shortest paths from node G in the above graph. The total number of edges which are not included in any of the shortest pat...
1 votes
1 votes
2 answers
3
Bikram asked May 26, 2017
457 views
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.
0 votes
0 votes
1 answer
4
Bikram asked May 26, 2017
304 views
Consider the following instance of the knapsack problem :$\begin{array}{|c|c|c|c|c|c|} \hline \text{Item} & a & b & c & d & e \\ \hline \text{Benefit} & 15 & 12 & 9 & 16 ...