Idea of Algorithmic Efficiency || Notes || Sumita Arora || Class 12 || Computer science
Note:- PDF Download link given below of this Blog
-: Idea of Algorithmic Efficiency :-
· Algorithm efficiency is related to the time taken by a program for execution and space used by the algorithm.
· Performance of algorithm depends on many internal and external factors.
· Internal Factors specify algorithm’s efficiency in terms of:
- Time required to run
- Space required to run
· 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
· Mainly internal factors control the algorithm’s efficiency.
· Computational Complexity refers to measure the efficiency of an algorithm or program in terms of space and time.
· The program which uses minimum number of resources, less space and minimum time, is known as good program.
· Time Complexity:
- It is the number of elementary instructions that the program executes.
- Number depends on the size of the input data.
- The time complexity of algorithms is most commonly expressed using the big O notation.
· Time Complexity of an algorithm:
- Best case: - The minimum number of steps that an algorithm can take for any input data values.
- Average case: - The efficiency averaged on all possible inputs. We normally assume the uniform distribution.
- Worst case: - The minimum number of steps that an algorithm can take for any input data values.
· 3 asymptotic notations are mostly used to represent time complexity of algorithms.
- Θ (theta notation): - To denote tight bound (best case)
- O (big oh notation): - To denote upper bound (worse case)
- Ω (omega notation): -To denote lower bound (average case)
· Big O Notation:
- The growth rate determines the algorithm’s performance when its input size grows.
- 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.
- Performance of the algorithms is inversely proportional to the wall clock time. Programs with a bigger O run slower than programs with a smaller O.
· Dominant term: if the algorithm’s performance is an2 +bn +c then we can say an2 is the dominant term which has maximum impact on algorithm’s performance
· Calculating complexity (Assumption: All steps take precisely take same time to execute.)
· Running time of loop is equal to the running time of statement inside the loop (including tests) multiplied by the number of iteration.
1. Loops:
for i in range(n):
m=m+2
So, the total time taken by above loop to execute itself is:
Total time =c*n=cn
c=time taken by n steps n=no of iterations
i.e complexity is O(n)
2. Nested Loops:
for i in range(n):
for j in range(n):
L=L+1
So, the total time taken by above nested loop to execute is:
Total time=c*n*n=cn2
I.e. complexity is O(n2)
3. Consecutive Statements:
a=a-1
for i in range(n):
m=m+2
for j in range(n):
for k in range(n):
b=b+1
So, the total time taken by above code to execute is:
Total time= c0+c1*n+c2*n*n=c0+c1n+c2n2
i.e complexity is O(n2)
4. if-then-else statements:
if(len(list1)!=len(list2):
return False
else:
for i in range(n):
if(list1[i]!=list2[i]):
return False
So, the total time taken by above code to execute is:
Total time=c0+c1+ (c2 + c3) *n=c0+c1++ (c2 + c3) n
I.e. complexity is O(n)
5. Logarithmic Complexity: It means that an algorithm’s performance has logarithmic factor e.g. Binary search O(log n)
· Growth rates order: O(1)<O(log n)<O(n)<O(nlogn)<O(n2) <O(n3) <O(2n)
· Wall Clock Time: The wall-clock time is not the number of seconds that the process has spent on the CPU; it is the elapsed time, including time spent waiting for its turn on the CPU (while other processes get to run).
Performance of algorithm is inversely proportional to the wall clock time it records for a given input size.
Normal Program (Without Recursion)
import time
start=time.time( )
num = int(input("Enter a number: "))
factorial = 1
if num < 0:
print("factorial does not exist for negative numbers")
elif num == 0:
print("The factorial of 0 is 1")
else:
for i in range(1, num + 1):
factorial = factorial*i
print("The factorial of",num,"is",factorial)
end=time.time()
t=end-start
print("Total time taken: ", t)
OUTPUT:-
Enter a number: 5
The factorial of 5 is 120
Total time taken: 5.615321159362793
Recursive Program
import time
def factorial(n):
if n == 1:
return n
else:
return n*factorial(n-1)
start=time.time()
num=int(input("enter the number: "))
if num < 0:
print("factorial does not exist for negative numbers")
elif num==0:
print("The factorial of 0 is 1")
else:
print("The factorial of ",num," is ", factorial(num))
end=time.time()
t=end-start
print("Total time taken: ", t)
OUTPUT:-
enter the number: 5
The factorial of 5 is 120
Total time taken: 2.149122714996338
· Recursive program is taking less time than without recursion program. So, Program with recursion is efficient. Therefore, we can conclude that Performance of algorithm is inversely proportional to the wall clock time.
Some important Questions
Q1. What is algorithm?
Answer = It is a step by step process to solve a problem.
Q2. What is Algorithm efficiency?
Answer = Algorithm efficiency is related to the time taken by a program for execution and space used by the algorithm.
Q3. 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.
Q4. Which factors affect an algorithm’s performance?
Answer = Time and space.
Q5. Which complexity is more O(n) or O(log n)?
Answer = O(n)
Q6. Is linear search or binary search faster?
Answer = Binary search
Q7. What is worst case in terms of algorithms?
Answer = The input that makes a given algorithm run slowest.
Q8. What is the best case in terms of algorithms?
Answer = The input that makes a given algorithm run fastest.
Q9. Reorder the following efficiencies from smallest to largest:
a)10000
b)n!
c) n2
d)nlogn
Answer = 10000<nlogn<n2 <n!
Q10. 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
Q11. 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
Q12. What is the time complexity of binary search?
Answer = O (log n)
Q13. 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)
Q14. 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.
Q15. Given the following array, which search will find the value 18 in least steps?
3 10 18 22 35
Answer = Binary search
Q16. Given the following array, which search will find the value 3 in least steps?
3 10 18 22 35
Answer = Linear search
Q17. Calculate the run-time efficiency of the following program segment:
i=1
while i<=n:
j=1
while j<=n:
k=1
while k<=n:
print(i,j,k)
k=k+1
j=j+1
i=i+1
Answer = O (n3)
Q18.
(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)
Thankyou!!!!!
For Solution of ‘Sumita Arora’ visit on Path Walla
For ‘Sumita Arora Type C’ solution (Programing Question) Visit our YouTube Channel Portal Express
Post a Comment
You can help us by Clicking on ads. ^_^
Please do not send spam comment : )