Problem 1 Consider the following code fragment. test n int (input (\"Input a num

Question

Problem 1 Consider the following code fragment. test 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 what is its Big-o running time (e.g. o(n), 0(nz),00gn), odn Ign) 0(n3))? Briefly explain Problem 2 Consider the following code fragment. test. 30 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. 0(n), 0(n2),0(lgn), 0(m lgn0,0(ma))? Briefly explain. Problem 3 Consider the following code fragment. n int (input ("Input a number while i >0: k 3 2 2 Answer the same questions as in Problem 2. Problem 4 For an input size of n, an algorithm executed n3 2m2 operations. What is the algorithm's Big-o running time?

Explanation / Answer

I am providing you the solution for first 3 questions. For remaining questions please post the question again.

Please give thumbs up to my answers.

Problem 1)

test=0
n=int(input("Number: ")
for i in range(n):
   for j in range(2*n):
       test=test+i*j

a) If n=100, test=test+i*j will execute 20000 times(100*2*100).

b) In terms of n, it will execute (n*2*n) times

c) Big-O running time is O(n2)

Problem 2)

test=0
n=int(input("Number: ")
for i in range(n):
   test=test+i
for j in range(2*n):
   test=test+i

a)

For, input n=100
First loop iterates for 100 times.
Second loop iterates for 200 times.
So, total loops will executes 300 times.

b) In terms of n, it will execute (n+(2*n)) times.

c) Big-O running time is O(n)

Problem 3)

n=int(input("Number: ")
i=n
while i>0:
   k=2+2
   i=i//2

a) if n=100, it will execute 7 times.

b) In terms of n, it will execute log2(n) times.

c) Big-O running time is O(log2(n))

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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