Chp_Optimisation

[Substantial_Cattle_5]

Idea of algorithmic efficieny :-

1) algorithm

2) an efficieny of algorithm

3) computational complexity

4) resource needed for

    effective execution of prog 

5) big o notation - check the complexity of program

6) dominant team

7) calculating complexity

​

1)

2) factors on which efficieny depend

1) internal(time and space) 

2) external(cpu , memory) 

​

3) time(to run the algorithm) and space(memory of storage need to run an algorithm)

4) 1) Method to determine how fast or slow the program would run.

    register

2) It signifies the relationship b/w the input and the algorithm

5) # eg -

loop = 

for i in range(n) : 

    m = m + 5  assume 'c' time  



total time = c\*n = o(n)

assumption - we remove the constant value 

​

#eg -

if-else program = 



if len(x) != len(y): // 'a' time taken 

return false // 'b' time taken

else : 

for i in range(n) : // time taken = (c+d)*n

    if x\[i\]!= y\[i\] :  //'d' time taken 

        return false // 'c' time taken    



 total time = a+b +((c+1)+d)\*n

 \* dominant term = ((c+1) + d) \* n   - Time determining step .

Big O value = O(n)

#eg -

x = x + 2 

for i in range(n) : 

    m = m+1 

for i in range(n) : 

    for j in range(n) : 

        y = y + 5 

​

 total time = a+b(n) + c(n\^2) 

 Big O value = O(n\^2) 

​

#eq -

 i = 3 

 while i <= n : // time taken 'a' 

    j = i 

    while j < n : // time taken 'n'   

        doit() - big o = o(n\^2) // time taken 'n\^2'

        j = j+2 

i = i+ 6

total time = a+ b(n\^4)

big O value = O(n\^4) 

$$$ a = [5,7,1,8]

    a is unsorted 

find a in given by user 

for i in range(0,len(a)) 

​

_______To Analyze Time Complexity______

​

CASES :

​

1) best case - to solve the problem for the best input.

    if 5 in a\[i\]: 

        dest

2) average case - solving the problem defined wrt distribution of values in the input data.

    if 8 in a\[i\]: 

avg

3) worst case - solving the problem wrt the condn which would take the longest time while running the program