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