Problem 1 Consider the following code fragment. test = 0 n = int(input(“Input a

Question

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 algorithm’s 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.  

Explanation / Answer

problem 1:solution as follows

a)

test=0

n=100

i=range(100) // means i value 100

j=2*100 // because n value 100

test=0+100*200

test=0+20000

test=20000

if n value is 100 the all statements should rotate in 20000 times

b)

test 0

n=n // in the proram states that n value is n

i=range(n) //i value remains n

j=2*n //j values remains 2n

test=0+n*2n

test=2n2 times  

so while taking n value as n the above all statements execute 2n2 times

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.