## 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=cn^{2}

I.e. complexity is O(n^{2})

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= c_{0}+c_{1}*n+c_{2}*n*n=c_{0}+c_{1}n+c_{2}n^{2}

i.e complexity is O(n^{2})

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=c_{0}+c_{1}+ (c_{2} + c_{3})
*n=c_{0}+c_{1}++ (c_{2} + c_{3}) 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(n^{2}) <O(n^{3}) <O(2^{n})

· **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(n^{2})

**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 (n^{3})

**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 (n^{2})

**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 : )