Below are the results of running a program with different size inputs. What is the most likely running time as a function of N
| N | Seconds |
|---|---|
| 640,000 | 0.19 |
| 1,280,000 | 0.40 |
| 2,560,000 | 0.80 |
| 5,120,000 | 1.61 |
| 10,240,000 | 3.31 |
| 20,480,000 | 6.76 |
| 40,960,000 | 13.85 |
| 81,920,000 | 27.33 |
O(1)
O(log n)
O(n)
O(n2)
O(n2 log n)
O(n3)
O(n!)
O(n)
Below are the results of running a program with different size inputs. What is the most likely running time as a function of N
| N | Seconds |
|---|---|
| 640,000 | 0.19 |
| 1,280,000 | 0.40 |
| 2,560,000 | 0.80 |
| 5,120,000 | 1.61 |
| 10,240,000 | 3.31 |
| 20,480,000 | 6.76 |
| 40,960,000 | 13.85 |
| 81,920,000 | 27.33 |
O(1)
O(log n)
O(n)
O(n2)
O(n2 log n)
O(n3)
O(n!)
O(n)
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(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
O(n!)
O(log n)
Using big-O notation what is the worst case running time of the function below?
def f14(a: list, i, j) :
temp = a[i]
a[i] = a[j]
a[j] = temp
O(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
O(n!)
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(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
O(n!)
O(n)
Using big-O notation what is the worst case running time of the function f10?
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 f10(a: list) :
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(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n^2 log n)
O(n3)
O(n!)
O(n^2 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)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
O(n!)
O(1)
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(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
O(n!)
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(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
O(n!)
O(n)
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(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n^3)
O(2n)
O(n!)
O(n^3)
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(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
O(n!)
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(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
O(n!)
O(n log n)
