Performance Analysis (a) Explain what a large problem is based on the definition
ID: 3824588 • Letter: P
Question
Performance Analysis (a) Explain what a large problem is based on the definition of the Big-Oh notion g(n) = O(f(n)). (b) Consider a procedure allShortest in C pseudo code. The procedure allShortest takes three inputs, cost, distance, and n Both cost and distance are a matrix which has n columns and n rows in total. The algorithm is to compute the shortest distance between any two positions, i and j (e.g. distance [i] [j]). void allShortest (int cost[] [], int distance [] [] int n) {int i j, k; for (i = 0; iExplanation / Answer
1.) Big-oh of a function f(n) is given as:
f(n) = O(g(n)) iff c*g(n) >= f(n) where c>0, n>=n0 and n0>0
The more is the value of g(n), the more is the time will be taken to solve the problem and hence, larger is the problem. It means depending on the value of g(n), we can predict whethter the problem is large or not.
2.) i.) In worst case analysis;
loop on line 3, will run on n times and due to which loop on line 4 runs on n^2 times. So, in overall, line 5 runs n^2 times.
Similarly, in worst case analysis, loop on line 6,7 and 8 are run n, n^2 and n^3 times respectively and line no. 10 runs n^3 times. So, overall g(n) = n^2 + n^3
ii.) For c = 10, no = 0,
10* n^3 >= g(n). Hence, g(n) = O(n^3).
Hope it helps, do give your response.