Problem 1 Consider the following code fragment. test = 0 n = int(input(Input a number: )) for i in range(n): for j in range(2 * n): test = test + i * j a. How many times does the statement test = test + i * j execute if n were 100? b. Express the number of times that the statement will execute in terms of n. c. What is its Big-O running time (e.g. , $ , (lg ), ( lg ), ()))? Briefly explain.

Problem 2 Consider the following code fragment. test = 0 n = int(input(Input a number: )) for i in range(n): test = test + i for j in range(2 * n): test = test + i a. How many times do the loops iterate in total for an input of 100? b. Express the total number of iterations that the loops execute in terms of n. c. What is its Big-O running time (e.g. , $ , (lg ), ( lg ), ()))? Briefly explain.

Problem 3 Consider the following code fragment. n = int(input(Input a number: )) i = n while i > 0: k = 2 + 2 i = i // 2 Answer the same questions as in Problem 2.

Problem 4 For an input size of n, an algorithm executed ) + 2$ operations. What is the algorithms Big-O running time?

Problem 5 To derive the Big-O running time of an algorithm, you execute it for a range of input sizes and measure the execution times. Suppose you obtain the results in the table below. Input size Execution time (sec) 2000 1.25 4000 4.89 6000 13.11 8000 20.73 10000 31.51 12000 55.21 Based on these measurements, what would you hypothesize its Big-O running time to be? Explain your answer.

Problem 6 Consider the following implementation of Bubble sort, which is considered to be an inefficient sorting method. def bubbleSort(alist): for passnum in range(len(alist)-1,0,-1): for i in range(passnum): if alist[i]>alist[i+1]: temp = alist[i] alist[i] = alist[i+1] alist[i+1] = temp You are to measure the execution time of this function for varying size inputs as follows: 1000, 2000, 3000, , 10000. For each test case, create a random list of integers and measure the execution time. Model your program after exec_time_np.py posted on piazza under Source Code. Save your program in a file named hwk3_6.py. Your program should output the list sizes and the corresponding execution times.