1. what is the Big-O performance of the following function? def sum(n): k = 0 fo
ID: 3827299 • Letter: 1
Question
1. what is the Big-O performance of the following function?
def sum(n):
k = 0
for i in range(n):
for j in range(n):
k = k + n
return k
a. O(1) b. O(n) c.O(n2) d.O(log n)
2. what is the Big-O performance of the following function?
def sum2(n):
i = n
k = 0
while i > 0:
k = k + 1
i = i // 2
return k
a. O(1) b. O(n) c.O(n2) d.O(log n)
3. what is the Big-O performance of the following function?
def sum(n):
k = 0
j = 0
while k < n:
k = k + 1
while j < n:
j = j + 1
k = k + j
return k
a. O(1) b. O(n) c.O(n2) d.O(log n)
4. what is the Big-O performance of the following function?
def sum3(n):
k = 0
for i in range (n):
k = k + i
for j in range (n):
k = k - j
return k
a. O(1) b. O(n) c.O(n2) d.O(log n)
5.what is the Big-O performance of the following function?
def sum3(n):
k = 0
for i in range (n):
k = k + i
return k
a. O(1) b. O(n) c.O(n2) d.O(log n)
Explanation / Answer
1. what is the Big-O performance of the following function?
def sum(n):
k = 0
for i in range(n):
for j in range(n):
k = k + n
return k
Ans: c.O(n2) : We have two nested for loop, each running n times
2. what is the Big-O performance of the following function?
def sum2(n):
i = n
k = 0
while i > 0:
k = k + 1
i = i // 2
return k
Ans: d.O(log n) : In each iteration, we are dividing k by 2
3. what is the Big-O performance of the following function?
def sum(n):
k = 0
j = 0
while k < n:
k = k + 1
while j < n:
j = j + 1
k = k + j
return k
Ans: b. O(n)
first while loop takes: n time and second while loop runs n times
So, n + n = 2n => O(n)
4. what is the Big-O performance of the following function?
def sum3(n):
k = 0
for i in range (n):
k = k + i
for j in range (n):
k = k - j
return k
Ans: b. O(n)
5.what is the Big-O performance of the following function?
def sum3(n):
k = 0
for i in range (n):
k = k + i
return k
Ans: b. O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.