Longest Common Subsequence (LCS) |
O ( M * N ). M and N are the lengths of the first and second sequence respectively. |
Longest Increasing Subsequence (LIS) |
O ( N 2 ). N is the number of elements in the sequence. |
Matrix Chain Multiplication |
O ( N 3 ). N is the number of matrices. |
Longest Palindromic Substring |
O ( N 2 ). N is the length of the string. |
Maximum Sum Subarray |
O ( N ). N is the number of elements in the subarray. |
0-1 Knapsack |
O ( N * M ). N is the capacity of the knapsack and M is the number of weights available for putting into the knapsack. |
Coins Change Problem |
O ( N * M ). N is the bigger coin to be exchanged and M is the number of smaller coins to be used for exchanging |
Integer Partitioning Problem |
O ( N * M ). N is the bigger number to be partitioned and M is the number of smaller integers to be used for partitioning. |
Maximum Sum SubRectangle using aggregate rectangles |
O ( N 4 ). N is the number of elements in the rows / columns in the rectangle. |
Maximum Sum SubRectangle using Kadane’s algorithm |
O ( N 3 ). N is the number of elements in the rows / columns in the rectangle. |