[go: up one dir, main page]
Scribd
Upload
25 views8 pages

Bscs-402 Data Structure Lab 1

This document compares three algorithms for calculating factorials: an iterative approach using a while loop, an iterative approach using a for loop, and a recursive approach. It designs the algorithms in Python, tests their performance on different input sizes using the timeit module, and analyzes their asymptotic time complexities using Big-O notation. The document finds that the iterative for loop approach is most efficient for the tested input sizes. However, all three algorithms have a time complexity of O(n). While recursion is more efficient numerically, it uses more stack space practically and is slower on a machine.

Uploaded by

Muhammad Anas Rashid
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
25 views8 pages

Bscs-402 Data Structure Lab 1

This document compares three algorithms for calculating factorials: an iterative approach using a while loop, an iterative approach using a for loop, and a recursive approach. It designs the algorithms in Python, tests their performance on different input sizes using the timeit module, and analyzes their asymptotic time complexities using Big-O notation. The document finds that the iterative for loop approach is most efficient for the tested input sizes. However, all three algorithms have a time complexity of O(n). While recursion is more efficient numerically, it uses more stack space practically and is slower on a machine.

Uploaded by

Muhammad Anas Rashid
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

BSCS-402 DATA STRUCTURE

LAB 1
Q1 . Your task is to design two different algorithms in
python/C++ which calculates factorial of a number entered
by user
(you may choose iterative and recursive approach)

Algorithm 1 while Loop (iterative)

def factorial1(N):
# N = input("Input Number : ")

i = int(N)
factorial = int(N)
while (i > 1):
i = i-1
factorial = factorial * i
return factorial

Page 1
Algorithm 2 For Loop (iterative)

def factorial2(N):
# N = input("Input Number : ")

i = int(N)
factorial = int(N)
for j in range(1,int(N)):
factorial = factorial * j

return factorial

Algorithm 3 (Recursive)

def factorial3(N):
"""This is a recursive function
to find the factorial of an integer"""

if N == 1:
return 1
else:
a = (N * factorial3(N - 1))

return a

Page 2
Q2.Compare the performance of the above two algorithms
by finding the time required to execute the algorithms (You
can use %timeit )

Efficiency Testing Algorithm

def Efficiency(Factorial,Times):

a = timeit.timeit(lambda :factorial1(Factorial), number =


Times) #1 Iteration with while loop
b = timeit.timeit(lambda :factorial2(Factorial), number =
Times) #2 Iteration with For loop
c = timeit.timeit(lambda :factorial3(Factorial), number =
Times) #3 Recursion

if a < b and a < c:


print (a ,"For Value ", i ," Iterative while loop is
Efficient")
elif b < a and b < c :
print(b,"For Value ", i ," Iterative For loop is Effiecient")
elif c < a and c < b :
print(c,"For Value ", i ,"Recursion is Efficient")
else:
print("Equal")

Page 3
Results of Algorithm

• For loop is running for factorial 1 till 100 with a leap of


10
• Each Factorial is running for 10000 times

for i in range ( 1,101,10):


Efficiency(i, 10000)
Serial Value Time/sec Conclusion
No 10-3
1 1 2.054 Recursion is Efficient
2 11 10.250 Iterative For loop is Effiecient
3 21 17.854 Iterative For loop is Effiecient
4 31 26.240 Iterative For loop is Effiecient
5 41 35.354 Iterative For loop is Effiecient
6 51 53.650 Iterative For loop is Effiecient
7 61 49.094 Iterative For loop is Effiecient
8 71 61.410 Iterative For loop is Effiecient
9 81 76.625 Iterative For loop is Effiecient
10 91 83.008 Iterative For loop is Effiecient

Page 4
Graphs Comparison

def mainPlot():
x= []
while1 = []
for1 = []
recur = []
for i in range (1,850):
x.append(i)
while1.append(timeit.timeit(lambda :factorial1(i),
number = 500))
for1.append(timeit.timeit(lambda: factorial2(i),
number=500))
recur.append(timeit.timeit(lambda: factorial3(i),
number=500))

graph.plot(x,while1)
graph.plot(x,for1)
graph.plot(x,recur)

graph.legend(["Iterative While Loop","Iterative for


Loop","Recursion"])
graph.ylabel(" Times/S ")
graph.xlabel(" Input Size ")

graph.show()
Value for factorial from 1 till 800
Each Value for factorial will run for 50 times

Page 5
Q3.Now compares the algorithmic efficiency using big-O
notation

College OPERATION ITERATION SUBTOTAL


i = int(N) 1 1 1

factorial = int(N) 1 1 1

while (i > 1): 1 n+1 n+1

i = i-1 2 n 2n

factorial = factorial * i 2 n 2n

Total 5n+3 = O(n)

College OPERATION ITERATION SUBTOTAL


i = int(N) 1 1 1

Page 6
factorial = int(N) 1 1 1

for j in range(1,int(N)): 2 n+1 2n+2

factorial = factorial * j 2 n 2n

Total 4n+3 = O(n)

College OPERATION ITERATION SUBTOTAL


if N == 1: 1 1 1

return 1 1 1 1

else: 1 n n

a = (N * factorial3(N - 1)) 3 n 3n

Total 4n+2 = O(n)

Conclusion:
▪ All Algorithms have same complexity of O(n).

▪ Although recursion prove to be more efficient numerically but practically it is using


too much Stack space which makes it slower on machine.

Page 7
Page 8

You might also like