Please do the following exercises using the instructionsgiven.

Exercise I (25 points) This exercise explores the concept of best, average, and worst cases for the time complexity. Consider the following problem: insertinSortedList Input: a number a and a sorted linked list L of numbers Output: a sorted list including a and L a) Propose in pseudocode an algorithm for insertinSortedList b) Propose an action to analyze the time complexity of insertinSortedList c) Is the time complexity constant for any problem instance? If not, determine and justify the time complexity for the best, average, and worst case d) How do the time complexities for the best case, average case, and worst case grow e) Analyze the space complexity. Is your algorithm in-place? What you need to do: Answer the questions and/or solve the exercises described below. uestions (15 points): a) For each of the following problems, propose the “action/operation” you would use to determine the time complexity (short answers are fine here). a. Find x in a list of names b. Transpose an n x n matrix M c. Multiply two n x n matrices d. Sort a list of numbers e. Traverse (to display e.g.) a binary tree (represented as a linked structure where each node contains pointers to its left and right children) Show transcribed image text Exercise I (25 points) This exercise explores the concept of best, average, and worst cases for the time complexity. Consider the following problem: insertinSortedList Input: a number a and a sorted linked list L of numbers Output: a sorted list including a and L a) Propose in pseudocode an algorithm for insertinSortedList b) Propose an action to analyze the time complexity of insertinSortedList c) Is the time complexity constant for any problem instance? If not, determine and justify the time complexity for the best, average, and worst case d) How do the time complexities for the best case, average case, and worst case grow e) Analyze the space complexity. Is your algorithm in-place?

What you need to do: Answer the questions and/or solve the exercises described below. uestions (15 points): a) For each of the following problems, propose the “action/operation” you would use to determine the time complexity (short answers are fine here). a. Find x in a list of names b. Transpose an n x n matrix M c. Multiply two n x n matrices d. Sort a list of numbers e. Traverse (to display e.g.) a binary tree (represented as a linked structure where each node contains pointers to its left and right children)

## Expert Answer

I)

**a)Algorithm for insertInSortedList**

**insertInSortedList(int L[],int n,int a,int capacity)**

**{**

if(n>=capacity) —>1

return n; —->1