What is the running time for this java code? I want the complexity and asymptotic upper bound using Big-Oh notation class lcs { static void LongestCommonArraySubsequence(int X[], int Y[], int n, int m) { // dp[][] array int[][] dp = new int[n + 1][m + 1]; // dp matrix initialization for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) dp[i][j] = 0; for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j >= 0; j--) { if (X[i] == Y[j]) dp[i][j] = dp[i + 1][j + 1] + 1; // bottom up fill } } int max = 0; // maximum length int Xindex = 0; // starting index of array X int Yindex = 0; // starting index of array Y for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // calculating the maximum value in dp matrix if (dp[i][j] > max) { max = dp[i][j]; Xindex = i; Yindex = j; } } } // output statements System.out.println(max); System.out.println(Xindex + 1);// index starts from 0 System.out.println(Yindex + 1);// index starts from 0 } // Driver Code public static void main(String[] args) { // input array int X[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 }; int Y[] = { 13, 15, 18, 1, 3, 5, 8, 10, 12, 20 }; int n = X.length; int m = Y.length; // method call LongestCommonArraySubsequence(X, Y, n, m); } }
What is the running time for this java code? I want the complexity and asymptotic upper bound using Big-Oh notation class lcs { static void LongestCommonArraySubsequence(int X[], int Y[], int n, int m) { // dp[][] array int[][] dp = new int[n + 1][m + 1]; // dp matrix initialization for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) dp[i][j] = 0; for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j >= 0; j--) { if (X[i] == Y[j]) dp[i][j] = dp[i + 1][j + 1] + 1; // bottom up fill } } int max = 0; // maximum length int Xindex = 0; // starting index of array X int Yindex = 0; // starting index of array Y for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // calculating the maximum value in dp matrix if (dp[i][j] > max) { max = dp[i][j]; Xindex = i; Yindex = j; } } } // output statements System.out.println(max); System.out.println(Xindex + 1);// index starts from 0 System.out.println(Yindex + 1);// index starts from 0 } // Driver Code public static void main(String[] args) { // input array int X[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 }; int Y[] = { 13, 15, 18, 1, 3, 5, 8, 10, 12, 20 }; int n = X.length; int m = Y.length; // method call LongestCommonArraySubsequence(X, Y, n, m); } }
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
What is the running time for this java code?
I want the complexity and asymptotic upper bound using Big-Oh notation
class lcs {
static void LongestCommonArraySubsequence(int X[], int Y[], int n, int m) {
// dp[][] array
int[][] dp = new int[n + 1][m + 1];
// dp matrix initialization
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
dp[i][j] = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
if (X[i] == Y[j])
dp[i][j] = dp[i + 1][j + 1] + 1; // bottom up fill
}
}
int max = 0; // maximum length
int Xindex = 0; // starting index of array X
int Yindex = 0; // starting index of array Y
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// calculating the maximum value in dp matrix
if (dp[i][j] > max) {
max = dp[i][j];
Xindex = i;
Yindex = j;
}
}
}
// output statements
System.out.println(max);
System.out.println(Xindex + 1);// index starts from 0
System.out.println(Yindex + 1);// index starts from 0
}
// Driver Code
public static void main(String[] args) {
// input array
int X[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
int Y[] = { 13, 15, 18, 1, 3, 5, 8, 10, 12, 20 };
int n = X.length;
int m = Y.length;
// method call
LongestCommonArraySubsequence(X, Y, n, m);
}
}
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education