Teachers and Examiners (CBSESkillEduction) collaborated to create the Idea of Efficiency in Python Class 12. All the important Information are taken from the NCERT Textbook Computer Science (083) class 12.
Idea of Efficiency in Python Class 12
Idea of Algorithmic Efficiency
A sufficiently accurate method or process that can be programmed into a computer and is used to carry out a given task is known as an algorithm. Numerous internal and external elements affect an algorithm’s performance, or should we say quality.
Internal Factors
a) Time required to run
b) Space required to run
External Factors
a) Size of the input to the algorithm
b) Speed of the computer on which it is run
c) Quality of the compiler
Idea of Efficiency in Python Class 12
What is computational complexity
When analysing algorithms, computational complexity is a important factor. The words “compulation” and “complexity” are combined to form the term “compulation complxity.” The computation includes the issues that need to be resolved and the algorithms used to do so. In order to understand how much resource is required or adequate for this algorithm to operate effectively, complexity theory is used.
The resource generally include
a) The time to run the algorithm
b) The space needed to run the algorithm
Estimating Complexity of Algorithms
Algorithmic complexity considers how quickly or slowly a specific algorithm operates. The mathematical function T(n) – time versus the input size n is how we define complexity. Without relying on implementation specifics, we wish to specify how long an algorithm takes.
Big-O Natation
Big O Notation is a technique for expressing how time-consuming an algorithm is. As the input increases, it calculates how long it will take to perform an algorithm. In other words, it determines an algorithm’s worst-case time complexity. The maximum runtime of an algorithm is expressed using the Big O Notation in data structures.
Idea of Efficiency in Python Class 12
Dominant Term
The growth rate is shown using the Big-O notation. By going inside the algorithm, one can find the category of mathematical formulas that most accurately captures the behaviour of an algorithm. The term that grows the quickest is the dominating term.
Common Growth Rates
Some growth rates of algorithms are as shown in following table –
a) O(1) – Constant
b) O(log N) – Log
c) O(N) – Linear
d) O(N log N) – n Log n
e) O(N2) – Quadratic
f) O(N3) – Cubic
g) O(2N) – Exponential
Idea of Efficiency in Python Class 12
Guidelines for Computing Complexity
The five guidelines for finding out the time complexity of a piece of code are –
a) Loops – The running time of a loop is , at most, equal to the running time of the stateemnts inside the loop multiplied by the number of iteration.
b) Nested Loops – To compute complexity of nested loops, analyze inside out. For nested loops, total running time is the product of the sizes of the loops.
c) Consecutive Statement – To compute the complexity of consecutive statement, simply add the time complexities of each statement.
d) If-then-else Statements – To compute time complexity of it-then-else statement, we consider worst-case running time, Which means, we consider the time taken by the test, plus taken by either the then part or the else part.
e) Logarithmic Complexity – The logarithmic complexity means that an algorithms performance time has logarithmic factor e.g. an algorithm is O(log N) if it takes a constant time to cut the problem size by a fraction.
Idea of Efficiency in Python Class 12
Best, Average and Worst case complexity
1) Best case – quickest turnaround time with optimal inputs. For instance, data that has already been sorted would be the best case scenario for a sorting algorithm.
2) Worst case – is the slowest completion speed, with pessimistic inputs.
3) Average case – mean equals average scenario.