Using big-O notation what is the worst case running time of the function below?
def f13(a: list) :
i = 0
while (i < len(a)) :
j = 0
while (j < len(a)) :
k = 0
while (k < len(a)) :
if (a[i] + a[j] + a[k] == 0) :
return True
k += 1
j += 1
i += 1
return False
O(N^3)
Using big-O notation what is the worst case running time of the function below?
def f13(a: list) :
i = 0
while (i < len(a)) :
j = 0
while (j < len(a)) :
k = 0
while (k < len(a)) :
if (a[i] + a[j] + a[k] == 0) :
return True
k += 1
j += 1
i += 1
return False
O(N^3)
Using big-O notation what is the worst case running time of the following?
def f8(a: list, t) :
lo = 0
hi = len(a) - 1
while (lo <= hi) :
m = int((lo + hi) / 2)
if (a[m] == t) :
return True
if (t < a[m]) :
hi = m - 1
else :
lo = m + 1
return False
O(log n)
Using big-O notation what is the worst case running time of the following?
def f5(N) :
count = 0
i = 0
while (i < N) :
j = 0
while (j < 10) :
count += i
j += 1
i += 1
return count
O(n)
Using big-O notation what is the worst case running time of the function f10S?
def f8(a: list, t) :
lo = 0
hi = len(a) - 1
while (lo <= hi) :
m = int((lo + hi) / 2)
if (a[m] == t) :
return True
if (t < a[m]) :
hi = m - 1
else :
lo = m + 1
return False
def f10S(a: list) :
a.sort()
i = 0
while i < len(a) :
j = 0
while j < len(a) :
if f8(a, -(a[i] + a[j])) :
return True
j += 1
i += 1
return False
O(N^3)
Using big-O notation what is the worst case running time of the following?
def f8(a: list, t) :
lo = 0
hi = len(a) - 1
while (lo <= hi) :
m = int((lo + hi) / 2)
if (a[m] == t) :
return True
if (t < a[m]) :
hi = m - 1
else :
lo = m + 1
return False
O(log n)
Using big-O notation what is the worst case running time of the following?
def f5(N) :
count = 0
i = 0
while (i < N) :
j = 0
while (j < 10) :
count += i
j += 1
i += 1
return count
O(N)
Using big-O notation what is the worst case running time of the function f10S?
def f8(a: list, t) :
lo = 0
hi = len(a) - 1
while (lo <= hi) :
m = int((lo + hi) / 2)
if (a[m] == t) :
return True
if (t < a[m]) :
hi = m - 1
else :
lo = m + 1
return False
def f10S(a: list) :
a.sort()
i = 0
while i < len(a) :
j = 0
while j < len(a) :
if f8(a, -(a[i] + a[j])) :
return True
j += 1
i += 1
return False
O(N^2 logN)
Using big-O notation what is the worst case running time of the function f16?
def f14(a: list, i, j) :
temp = a[i]
a[i] = a[j]
a[j] = temp
def f15(a: list, start) :
result = start
i = start + 1
while (i < len(a)) :
if (a[i] < result) :
result = a[i]
i += 1
return result
def f16(a: list) :
i = 0
while (i < len(a) - 1) :
f14(a, i, f15(a, i))
i += 1
O(N^2)
Using big-O notation what is the worst case running time of the following?
def f3(N) :
count = 0
i = 0
while i < N :
j = 0
while j < N :
count += i
j += 1
i += 1
return count
O(N^2)
Using big-O notation what is the worst case running time of the following?
def f7(N) :
count = 0
i = 1
while (i < N) :
count += i
i = i * 2
return count
O(log n)
Using big-O notation what is the worst case running time of the following?
def f4() :
count = 0
i = 0
while i < 100 :
count += i
i += 1
return count
O(1)
Using big-O notation what is the worst case running time of the following?
def f2(N) :
count = 0
i = 0
while i < N :
count += i
i += 1
return count
O(N)
Using big-O notation what is the worst case running time of the following?
def f6(N) :
count = 0
i = 0
while (i < N) :
count += i
i = i + 2
return count
O(N)
Using big-O notation what is the worst case running time of the function f9?
def f8(a: list, t) :
lo = 0
hi = len(a) - 1
while (lo <= hi) :
m = int((lo + hi) / 2)
if (a[m] == t) :
return True
if (t < a[m]) :
hi = m - 1
else :
lo = m + 1
return False
def f9(a: list) :
for value in a :
if (f8(a, -value)) :
return True
return False
O(n log n)
Using big-O notation what is the worst case running time of the following?
def f1(a: list, target) :
i = 0
while i < len(a) :
if a[i] == target :
return i
i += 1
return -1
O(N)
Using big-O notation what is the worst case running time of the function f12?
def f11(N) :
count = 0
while (N > 1) :
N //= 2
count += 1
return count
def f12(N) :
sum = 0
i = 0
while (i < N) :
sum += f11(N)
i += 1
return sum
O(n logn)
Using big-O notation what is the worst case running time of the function below?
def f15(a: list, start) :
result = start
i = start + 1
while (i < len(a)) :
if (a[i] < result) :
result = a[i]
i += 1
return result
O(N)
