Question 2. [8 points=4+41 Consider the following algorithm given in Java code: 1. boolean orderedPrefixes (String...

Transcribed Image Text:

Question 2. [8 points=4+41 Consider the following algorithm given in Java code: 1. boolean orderedPrefixes (String s) { 2. // Input: an string S of length 3. // Output: print all sorted boolean valid-true; int nos. length(); with letters prefixes of S and return true if S is sorted 4. System.out.println(s.charAt(0)); n; i++) { for (int i 1 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. if (s.charAt(i-1)> s.charAt(i)) { d = false; break; 19. for (int j=0; j<= i; j++) System.out.print(s.charAt(j)); System.out.println(); } } return valid; } Subject to mehr Note: when giving the big-Oh, give the tightest upper bound possible. For example, if you can prove that f(n) is 0(n), and that f(n) is 0(n²), choose the tighter upper bound, i.e. f(n) is O(n). (a) (4 pts) Give a big-Oh for T(n), the worst-case running time of this algorithm for an input string of length n. Explain how you obtained this worst case. (b) (4 pts) Give a big-Oh for B(n), the best-case running time of this algorithm for an input string of length n. Explain the type of inputs (sample inputs) that will give this case. Question 2. [8 points=4+41 Consider the following algorithm given in Java code: 1. boolean orderedPrefixes (String s) { 2. // Input: an string S of length 3. // Output: print all sorted boolean valid-true; int nos. length(); with letters prefixes of S and return true if S is sorted 4. System.out.println(s.charAt(0)); n; i++) { for (int i 1 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. if (s.charAt(i-1)> s.charAt(i)) { d = false; break; 19. for (int j=0; j<= i; j++) System.out.print(s.charAt(j)); System.out.println(); } } return valid; } Subject to mehr Note: when giving the big-Oh, give the tightest upper bound possible. For example, if you can prove that f(n) is 0(n), and that f(n) is 0(n²), choose the tighter upper bound, i.e. f(n) is O(n). (a) (4 pts) Give a big-Oh for T(n), the worst-case running time of this algorithm for an input string of length n. Explain how you obtained this worst case. (b) (4 pts) Give a big-Oh for B(n), the best-case running time of this algorithm for an input string of length n. Explain the type of inputs (sample inputs) that will give this case.

Answer rating: 100% (QA)

a The worstcase running time Tn of this algorithm is On2 This occurs when the input string is in descending order which causes the inner for loop to execute the maximum number of times Specifically th... View the full answer