Question

Find the Asymptotic time complexity for each of the functions in the following:

#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

Solution for the problem is provided below, please comment if any doubts:

#1.

Answer: O(l)

Explanation:

• Here the code segment consists of two “for” loops.
• Both the loops are in serial, thus complexities will be added, so the large for loop will constitute the upper limit complexity of the code.
• First for loop traverse the list “l” and second for loop traverse lost “m”.
• List “l” is larger than “m”, thus asymptotic complexity will be = O(l)

#2.

Answer: O(lm)

Explanation:

• Here also two “for” loops are there, but the second loop executes inside the first “for” loop.
• Thus second “for” loop needed to be executed “l” times and “m” times itself for each time.
• Thus total execution of “for” loops will be “l*m”
• Thus asymptotic complexity will be = O(lm)

#3.

Answer: O(log (l))

Explanation:

• Here the complexity determining part is the while loop.
• The while loop executes whenever “l>0”, but the “l” is reduced by “/2” at each run.
• Thus “l” will be reduced to half at each iteration.
• Thus total iterations will be = log(l).
• The asymptotic complexity will be = O(log l)

#4.

Answer: O(log(l)*√m)

Explanation:

• Here two level “while” loops will determine the complexity of the code.
• First while loop is same as previous code, thus it will run in “log l” iterations.
• The second while loop will be executes when m1*m1<m, thus it is in the terms of square root (m).
• Thus total iterations will be = log(l)*√m.
• The asymptotic complexity will be = O(log(l)*√m)

#5.

Answer: O(l*√m)

Explanation:

• Here also two level while loops are there.
• The first loop will execute in O(l), since it will execute whenever l²>0, it breakes only when l reaches 1.
• The inner while loop will be executes when m1*m1<m, thus it is in the terms of square root (m).
• The asymptotic complexity will be = O(l*√m)

#6.

Answer: O(a)

Explanation:

• Here the number of executions will be based on the equation sum+=b and sum<=a.
• Thus total number of executions = a-sum-b.
• Here the large value is a.
• The asymptotic complexity will be = O(a)