In [5]:
import numpy as np
Find the time complexity of the following:
Q1¶
a = 0
b = 0
for i in range(N):
a = a + i
for j in range(M):
b = b + j
Q2¶
a = 0
for i in range(N):
for j in range(N):
a = a + i + j
Q3¶
if a > b:
return True
else:
return False
In [ ]:
Write your answer here:
Q4¶
def binary_search(data, value):
n = len(data)
left = 0
right = n - 1
while left <= right:
middle = (left + right) // 2
if value < data[middle]:
right = middle - 1
elif value > data[middle]:
left = middle + 1
else:
return middle
Q5¶
L = np.random.rand(100)
for i in range(0,100):
print("My random number is: ", L[i])
In [ ]:
Write your answer here:
Q6¶
L = [1,2,3,4,5]
L[0] = L[0]+1
L[1] = L[1]+2
L[2] = L[2]+3
L[3] = L[3]+4
L[4] = L[4]+5
In [ ]:
Write your answer here:
Q7¶
def loop(K):
for i in range(k):
print(i)
for j in range(10):
loop(j)
In [ ]:
Write your answer here:
Q8¶
L = np.ones((100,100))
for i in range(0,100):
for j in range(0,100):
L[i][j] = L[i][j] + i + j
In [ ]:
Write your answer here:
Q9¶
for i in range(0,20):
for j in range(i,20):
print("*",end="")
print("")
In [ ]:
Write your answer here:
Q10¶
for i in range(0,20):
for j in range(i,20):
for k in range(j,20):
print("*",end="")
print("")
In [ ]:
Write your answer here:
Q11¶
Assume that each of the expressions below gives the processing time T(n) spent by an algorithm for solving a problem of size n. Select the dominant term(s) having the steepest increase in n and specify the lowest Time complexity of each algorithm.
Q2 Time vs Space¶
Below are two methods that solve the same problem(finding how many times each number appears in a list of numbers).
Check out the two provided methods and try to find the differences. What is the time complexity of each and how much memory does each one use?
for i in range(100):
L[i] = int(np.random.rand()*50)
#Method 1
for i in range(50):
count = 0
for j in range(100):
if(L[j] == i):
count = count + 1
print(count, end=" ")
#Method 2
count = np.zeros(50)
for i in range(100):
count[int(L[i])] = count[int(L[i])] + 1
print(count)
In [ ]:
Write your answer here:
Method 1:
Time:
Space:
Method 2:
Time:
Space: