CSC 172 Data Structures and AlgorithmsProblems samplesProblem 1:a. Express the order of running time for the following code using the big-Oh notation. Assume n is the size of the problem and it is given in input by the user. (4 points)public class PrintStars { private static void printStars(int ns) { int i; System.out.println(""); for(i = 0; i < ns; i++) System.out.print("*"); } public static void main(String[] args) { int j, n; //assume n is given in input by user PrintStars ps = new PrintStars(); for(j = 1; j <= n; j++) PrintStars.printStars(j); }}b. (*) Prove or disprove the following using the definition for the big-Oh notation:1. 2n+1 = O(2n) (meaning 2n+1 is O(2n) (2 points)2. 22n = O(2n) (meaning 22n is O(2n)) (2 points)CSC 172 Samples 1Problem 2:Show the list configuration resulting from the series of list operations using the List ADTwe’ve seen in lecture. Assume list L is empty at the beginning of the series. Show how the listchanges after each operation (on the right of the operation) including the symbol | for thecurrent position. (4 points)L.append(10);L.append(20);L.append(15);L.moveToStart();L.insert(39);L.next();L.insert(12); <39 | 12, 10, 20, 15>Q.enqueue(X);}}CSC 172 Samples 2Problem 3:a. Draw on the left the BST that results from adding the value 21 into the BST of Figure 1. (3points)(Draw here)Figure 1b. Give an enumeration (listing) of the values stored in the BST of Figure 1 using an inordertraversal of the tree. (3 points)1 3 4 6 7 8 10 13 14c. Give an enumeration (listing) of the values stored in the BST of Figure 1 using a postordertraversal of the tree. (3 points)Problem 4:Illustrate the operation of inserting the value 10 on the max-heap A = <15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1>. Show the values in the heap and a pointer to thecurrent element before each iteration of the main loop (while). Feel free to use the tree or thearray representation of the heap. (4 points)Note: You can use the back of page 5 to write your answer.Good luck!CSC 172 Samples 3// (can use this page as scrap paper)CSC 172 Samples