Idea of Algorithmic Efficiency in Python, Assignment Solutions for Computer Science Class 12. Here is solved Questions Answers and assignment of algorithmic complexity calculation of NCERT syllabus Sumita Arora book.
Idea of Algorithmic Efficiency in Python Class 12 Solutions
Short Answer Questions/ Conceptual Questions
Q.1.What is an algorithm? What do you understand by algorithm performance?
Answer:
An algorithm is sequence of steps carried out for the completion of program. Algorithm performance means for any of the allowed inputs, output are correct in shorter duration of time and consume less memory (system power).
Q.2.What is computational complexity?
Answer:
In computational complexity is the resources used of a computer to carry out a algorithm.
Q.3.Which factors affect an algorithm performance?
Answer:
Internal factors-
1.Time required to run.
2.Space required to run.
External Factors-
1.Size of the input to the algorithm
2.Speed of the computer on which it is run
3.Quality of the compiler
Q.4.What are different types of complexities that are considered?
Answer:
1.Time taken
2.Amount of space
Q.5.What do you understand by Big-O notation? What is its significance?
Answer:
The Big-O notation is used to depict an algorithm’s growth rate. The growth rate determines the algorithm’s performance when its input size grows.
Q.6.What do you understand by best-case, worst-case and average case complexities? When are they considered?
Answer:
Best-case – Running time of an algorithm in case of optimal performance.
Average-case- Expected running time of an algorithm.
Worst-case- Upper bound on running time of an algorithm
Q.7.Determine the Big-O notation for the following calculated complexity:
a)5n2.5 +n0.4
Answer: 5*n2.5
b)6log2(n)+9n
Answer: 9*n
c)3n4+nlog2(n)
Answer: n4
d)5n2+n3/2
Answer: n2
Q.8.Reorder the following efficiencies from the smallest to the largest:
a)2n b)n! c)n5 d)10,000 e) nlog2(n)
Answer:
10,000< nlog2(n) < n5 <2n < n!
Q.9.Reorder the following efficiencies from smallest to the largest:
(a)nlog2 n b)n+n2 +n3 c)24 d)n0.5
Answer:
24 < n0.5 <nlog2 n < n+n2 +n3
Q.10.Determine the Big-O notation for the following :
a)5n2.5 +n0.4
Answer: n2.5
b)6log2(n)+9n
Answer: n
c)3n4+nlog2(n)
Answer: n4
d)5n2+n3/2
Answer: n2
Q.11.Given that the efficiency of an algorithm is 5n2 ,if a step in this algorithm takes 1 nanosecond(10-9 ),how long does it take the algorithm to process an input of size 1000?
Answer:
5*(1000)2 *10 -9 =5*10-3 seconds
Q.12.Given that the efficiency of an algorithm is n3 ,if a step in this algorithm takes 1 nanosecond(10-9 ),how long does it take the algorithm to process an input of size 1000?
Answer: 10003*10-9 =1 seconds
Q.13.Given that the efficiency of an algorithm is 5nlog2 (n),if a step in this algorithm takes 1 nanosecond(10-9 ),how long does it take the algorithm to process an input of size 1000?
Answer:
5*1000*log2 (1000)*10-9 =5* log2 (1000) *10-6 seconds
Application Based Questions : Idea of Algorithmic Efficiency Class 12 Solutions
Q1.Calculate the run-time efficiency of the following program segment:
i=1
while i <=n:
print(i)
i=i+1
Answer:
O(n)
Q2. Calculate the run-time efficiency of the following program segment:
i=1
while i <=n:
j=1
while j<=n:
k=1
while j<=n:
print(i,j,k)
k=k+1
j=j+1
i=i+1
Answer:
O(n3)
Q3.IF the function dolt() has an efficiency factor of 5n, calculate the run-time efficiency of the following program segment.
i=1
while i<=n:
doIt(…)
i=i+1
Answer:
O(5n2)
Q4.If the efficiency of the function doIt() can be expressed as O(n2),calculate the efficency of the following program segment.
i=1
while i<=n:
j=1
while j<n:
doIt(…)
j=j+1
i=i+1
Answer:
O(n4)
Q.5.If the efficiency of the function doIt() can be expressed as O(n2),calculate the efficiency of the following program segment.
i=1
while i<n:
doIt(…)
i=i*2
Answer:
n3
Q.6.Given three list A,B,C of appropriate size , what is the complexity of following code in terms of n?
i=x=n
while i>0:
i=i-1
x+=A[i]
Answer:
n
Q.7. Given three list A,B,C of appropriate sizes, what is the complexity of following code in terms of n,m and p ?
for i in range (n):
for k in range (p):
x=0
for j in range(m)
x=+=A[i]*b[k]
Answer:
n*p*m
Q.8. Given integer variable x and a list A of appropriate size, What is the complexity of following code in terms of n ?
p=-1
q=n
while p+1<q:
m=(p+q)/2
if A[m]<x:
p=m
else:
q=m
Answer:
log2n
Q.9. Given a list A of appropriate size, what is the complexity of following code in terms of n?
m= A[0]
for i in range (n):
if A[i]>m:
m=A[i]
k=0
for i in range(n):
if A[i]==m:
k=k+1
Answer:
O(n)
Q.10. Given a list A of appropriate size, what is the complexity of following code in terms of n ?
for I in range(n-1,0,-1):
x=A[I]
A[I]=A[0]
p=0
while True:
c=2*p+1
if c>=I:
break
if c!=I-1 and A[c]<A[c-1]:
c=c+1
if x>=A[c]:
break
A[p]=A[c]
p=c
A[p]=x
Answer:
O(n2)
Q.11.Given a list A of appropriate size , what is the complexity in terms of n?
i=x=n
while i>0:
i=i-1
x=x+A[i]
Answer:
O(n)
Q.12.Given integer variable x and a list A of appropriate size, what is the complexity of following code in terms of n?
p=-1
q=n
while (p+1)<q:
m=(p+q)/2
if a[m],x:
p=m
else:
q=m
Answer:
log2(n)
Q.13. Given a list A of appropriate size, what is the complexity in terms of n?
m=a[0}
for I in range(n):
if a[i]>m:
m=A[i]
k=0
for i in range(n):
if A[i]==m:
k=k+1
Answer:
O(n)
Q.14.What is the time complexity of following algorithm?
(i) Insertion Sort
Answer:
O(n2)
(ii)Binary Search
Answer:
O(log2 n)
(iii) linear search
Answer:
O(n)
Q.15.Based on the the complexity analysis, which sorting algorithm is more efficient and why?
Answer:
Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
We are also providing the solutions of all the chapters of Computer Science (Python) in this site. the links of relevant topics are provided below:
Computer Science with Python Class 12 Sumita Arora Solutions – CS Study