Question

Hi, I am having trouble with trying to calculate asymptotic time complexity for each of these functions. A step by step tutorial would be great. This is done in Python. Please not only the answer, but how you calculated it as well.

Here is the code

#Q2
	# to denote ayymptotic time complexity use the following notation
	# O(l) O(m) O(a) O(b)
	# e.g. traversing through l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] is O(l)
	#1
	def merge():
	l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	m = [15, 16, 17, 18]
	lm = []
	for l_i in l:
	lm.append(l_i)
	for m_i in m:
	lm.append(m_i)
	print("lm:{}".format(lm))
	#2
	def merge_a_lot():
	l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	m = [15, 16, 17, 18]
	lm = []
	for l_i in l:
	lm.append(l_i)
	for m_i in m:
	lm.append(m_i)
	print("lm:{}".format(lm))
	#3
	def go_through():
	l = 10
	lm = []
	while l>0:
	lm.append(l)
	l=int(l/2)
	print("lm:{}".format(lm))
	#4
	def go_through_two():
	l = 10
	m = 5
	lm = []
	while l > 0:
	lm.append(l)
	l = int(l/2)
	m1=1
	while m1*m1 <= m:
	print("in")
	lm.append(m1)
	m1 +=1
	print("lm:{}".format(lm))
	#5
	def go_through_cross_two():
	l = 10
	m = 5
	lm = []
	while l*l > 1:
	lm.append(l)
	l -= 1
	m1 = 1
	while m1*m1 <= m:
	lm.append(m1)
	m1 += 1
	print("lm:{}".format(lm))
	#6
	def times():
	a=100
	b=5
	sum=b
	count=0
	while sum<=a:
	sum+=b
	count+=1
	print("count:{}".format(count))

Answer 1

#1 The very first loop runs for the number of times elements in l and then similarly for m. When two loops runs one after another, their time complexity is added So,

Time complexity = O(l+m)

#2 In this part, the second loop is inside the first loop, So, the second loop will run m times in every iteration of l. When two loops runs one inside other, their time complexity is multiplied. So,

Time complexity = O(l*m)

#3 In this part, the value of l is halved each time in the loop. So, it will take log₂l iterations to stop. So,

Time Complexity = O(log₂l)

#4 In this part, there are 2 different loops, the first loop runs for log₂l times while 2nd loop will run for sqrt(m) times. So,\

Time complexity = O(log₂l + sqrt(m))

#5 In this part, the second loop is inside the first loop so, time will be multiplied. So,

Time complexity = (log₂l * sqrt(m)

#6 This loop will run until the multiple of b becomes equal to a. So,

Time Complexity = O(a/b)