Homework SourseWanted to check my answers Please show work if wrong other w
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) |
Solution
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)
