Wanted to check my answers: Please show work if wrong other wise. I\'m really co
ID: 3934800 • Letter: W
Question
Wanted to check my answers: Please show work if wrong other wise. I'm really confused on 2.
for 1.) I got D.
for 2.) I beleive it is C.
????? 1) Give the best (i.e., lowest) big-O estimate for the number of operations (where an operation is an addition or a multiplication) used in this segment of an algorithm:
t := 0
for i = 1 to n
for j = 1 to n
t := (i * t + j * t + 1)2
O(1)
O(log(n))
O(n)
O(n2)
O(n3)
O(n4)
?????Give the best (i.e., lowest) big-O estimate for the number of print statements in the following:
i := 1
while i n
j := 1
while j i
print “hello”
j := j + 1
i := i + 1
O(1)
O(log(n))
O(n)
O(n2)
O(n3)
O(n4)
A)O(1)
B)O(log(n))
C)O(n)
D)O(n2)
E)O(n3)
F)O(n4)
Explanation / Answer
1)
Number of operation = n* n* 5 = 5n2 = O(n2)
Answer : D) O(n2)
2)
Number of prints = 1 + 2 + 3 + ... + n = n(n+1) / 2 = O(n2)
Answer : D) O(n2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.