CBSE Class 12 Computer Science Idea Of Efficiency Assignment

Very Short Answer Type Questions :

Question: Which factors affect an algorithm’s performance?
Answer: Time and space.

Question: Which complexity is more O(n) or O(log n)?
Answer: O(n)

Question: What is algorithm?
Answer: It is a step by step process to solve a problem.

Question: What is the best case in terms of algorithms?
Answer: The input that makes a given algorithm run fastest.

Question: What is Algorithm efficiency?
Answer: Algorithm efficiency is related to the time taken by a program for execution and space used by the algorithm.

Question: Is linear search or binary search faster?
Answer: Binary search

Question: What is worst case in terms of algorithms?
Answer: The input that makes a given algorithm run slowest.

Question: Define Big ‘O’ notation.
Answer: It is the upper bound of an algorithm’s performance i.e. if we say an algorithm takes O(n2) time: this means that this algorithm will carry out its task taking at most n2 steps for input size n.

Question: Name the External Factors that affects algorithm’s efficiency.
Answer: External Factors affecting algorithm efficiency are:
• Size of the input to the algorithm
• Speed of the computer on which it is run
• Quality of the compiler

Question: What is the time complexity of binary search?
Answer: O(log n)

Question: Reorder the following efficiencies from smallest to largest:
a)10000 b)n! c) n2 d)nlogn
Answer: 10000<nlogn<n2 <n!

Question: Given the following array, which search will find the value 18 in least steps?
3 10 18 22 35
Answer: Binary search

Question: a) What is the worst case complexity of the following code fragment?
for x in range(a):
statements
for y in range(b):
for z in range( c) :
statements
b) How would the complexity would change if a,b,c are replaced by n?
Answer: a) O(a+bc)b)O(n2 )

Question: Given the following array, which search will find the value 3 in least steps?
3 10 18 22 35
Answer: Linear search

Question: Calculate the run-time efficiency of the following program segment:
i=1
while i<=n:
while j<=n:
k=1
while k<=n:
print(i,j,k)
k=k+1
j=j+1
i=i+1
Answer: O(n3)

Question: Name the Internal Factors that affects algorithm’s efficiency.
Answer: Internal Factors specify algorithm’s efficiency in terms of:
♦ Time required to run
♦ Space required to run

Question: Write two suggestions that can be useful in designing algorithms.
Answer: (i) Redundant computations or unnecessary use of storage should be avoided.
(ii) Inefficiency due to late termination should be taken care of.

Question: Determine the complexity:

a) n=int(input(“Enter the number to check”))
flag=0
for i in range(2,n):
if n%i==0:
flag=1
break
if flag:
print(n,”is Not a prime number”)
else:
print(n,” is prime number”)
Answer: O(n)

b) n=int(input(“Enter the number to check”))
flag=1
i=2
while(i*i<=n):
if n%i==0:
flag=0
break
i=i+1
if flag:
print(n,”is Not a prime number”)
else:
print(n,” is prime number”)
Answer: O(n)

c) for i in range(n):
a=i+i+2
print(a)
for j in range(m):
b=b*4
print(b)
Answer: O(n+m)

d) for i in range(n):
for j in range(n):
a=i+j
print(a)
for k in range(n):
print(k)
Answer: O(n2)