Importance of Algorithm Analysis
What is an algorithm?
An algorithm is a finite set of instructions that, if followed, accomplishes a
Particular task. In addition, all algorithms must satisfy the following criteria:
1. Input:-There are zero or more quantities that are externally supplied.
2. Output:- At least one quantity is produced.
3. Definiteness:- Each instruction is clear and unambiguous.
4. Finiteness:- If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps.
5. Effectiveness:-Every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper. It is not enough that each operation is definite as in (3); it also must be feasible.
Why Analyse an Algorithm?
The most straightforward reason for analyzing an algorithm is to discover its characteristics in order to evaluate its suitability for various applications or compare it with other algorithms for the same application. Moreover, the analysis of an algorithm can help us understand it better, and can suggest informed improvements. Algorithms tend to become shorter, simpler, and more elegant during the analysis process.
What does an analysis of an algorithm?
To go from city “A” to city “B”, there can be many ways of accomplishing this: by flight, by bus, by train and also by bicycle. Depending on the availability and convenience, we choose the one that suits us. Similarly, in computer science, multiple algorithms are available for solving the
Same problem (for example, a sorting problem has many algorithms, like insertion sort, selection sort, quick sort, and many more). Algorithm analysis helps us to determine which algorithm is most efficient in terms of time and space consumed.
Types of analysis of algorithms
To analyze the given algorithm, we need to know with which inputs the algorithm takes less time (performing well) and with which inputs the algorithm takes a long time. Algorithm expression where we represent the algorithm with multiple expressions: one for the case where it takes less time and another for the case where it takes more time.
In general, the first case is called the best case and the second case is called the worst case for the algorithm. To analyze an algorithm we need some kind of syntax, and that forms the base for asymptotic analysis/notation. There are three types of analysis:
Worst case
○ Defines the input for which the algorithm takes a long time (slowest
Time to complete).
○ Input is the one for which the algorithm runs the slowest.
Best case
○ Defines the input for which the algorithm takes the least time (fastest
Time to complete).
○ Input is the one for which the algorithm runs the fastest.
Average case
○ Provides a prediction about the running time of the algorithm.
○ Run the algorithm many times, using many different inputs that come
from some distribution that generates these inputs, compute the total
running time (by adding the individual times), and divide by the
the number of trials.
○ Assumes that the input is random.
Lower Bound <= Average Time <= Upper Bound
For a given algorithm, we can represent the best, worst and average cases in the form of expressions. As an example, let f(n) be the function that represents the given algorithm.
Similarly for the average case. The expression defines the inputs with which the algorithm takes the average running time (or memory).
Algorithms are mainly used for mathematical and computer programs, whilst flowcharts can be used to describe all sorts of processes: business, educational, personal, and algorithms. So flowcharts are often used as a program planning tool to organize the program's step-by-step process visually. Here are some examples:
Examples of algorithms
Question:- Find the sum of the first 50 numbers
Solution:- Summing two numbers was easy – the calculation was one block from the flow chart. But how about 50? Do you have to write 50 blocks to solve this task?
Happily – No…!!!
You can automatize this process by repeatedly incrementing the value of a variable and checking it every time if it exceeds the last value – 50. Then sum that number every step and... there you go! This construction is called loop
Algorithm:
Step 1: start
Step 2: initialize three variables for values(num1, num2, sum)
Step 3: store value int variable num1 and num2
Step 4: perform addition operation between two variables
Step 5: store result into a variable sum
Step 6: print sum
Step 7: stop
Flowchart :
Example no 2:-
Question:- Find if a given number “n” is odd or even
Solution:-A number is even if it can be divided by 2 without remainder. Such numbers are 2, 4, 6, 8.. and so on. The numbers that leave a remainder are called odd. They are 1, 3, 5, 7.. and so on.
In programming, we find the remainder of a division with the operator %. Also, we use the double equals “==” to compare values for equality. You can read more about operators in the math operators lesson.
Algorithm:-
Step 1:Start
Step 2: initialize n
Step 3:check remainder = n% 2
Step 4: if remainder ==0 then print n is even
Step 5:if remainder ==0 is not eqal to then print n is ODD
Step 6:stop
Flowchart:-
Run time analysis:-
The runtime analysis tools are designed to closely monitor the behavior of your application for debugging and validation purposes. These features use source code insertion to instrument the source code provides a dynamic analysis of the application while it is running, either on a native or embedded target platform
Algorithm analysis is the science of knowing how complex an algorithm is in terms of time and space. The analysis of an algorithm can help us understand it better and can suggest informed improvements. Analyzing an algorithm is to discover its characteristics in order to evaluate its suitability for various applications.
Types of Notations :
1. Omega(Ω) Notation :
The notation Ω(n) is the formal way to express the lower bound of an algorithm’s running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.
For eg: let’s say we are sorting 1000 numbers, so the minimum time required to sort 1000 numbers is “10 secs”. In omega notation, those 1000 numbers cannot be sorted in less than 10 secs. It can be 11 secs, 12 secs but not 9 or 8 secs.
2. Big-o(O) Notation :
The big-o is the formal way to express the upper bound of an algorithm’s running time. It measures the worst-case time complexity or the maximum amount of time an algorithm can possibly take to complete.
For eg : let’s say we are sorting 1000 numbers again, so the maximum time required to sort 1000 numbers is “50 secs”. In big-o notation, those 1000 numbers can be sorted in less than 50 secs. It can be 48 secs, 46 secs but not 51 or 52 secs.
3. Theta(Θ) Notation :
The theta notation bounds a function from above and below, so it defines exactly asymptotic behavior. For any given input, the running time of a given algorithm will “on an average” be equal to a given time.
For e.g.: let’s take again the example of sorting 1000 numbers, for the first time the algorithm takes 10 sec, if we sort it again it takes 11 sec, and again if we sort for the 3rd time it takes 7 sec.
Runtime or dynamic memory allocation:-
Memory allocated at runtime either through malloc(), calloc() or realloc() is called runtime memory allocation. You can also refer to runtime memory allocation as dynamic or heap memory allocation.
Professional programmers prefer dynamic memory allocation moreover static memory allocation. Since we have full control over the allocated memory. This means we can allocate, deallocate, and can also reallocate memory when needed.
Compile-time vs. runtime memory allocation difference
Compile-time memory allocation | Runtime memory allocation |
Memory is allocated during program compilation. | Memory is allocated during runtime. |
You cannot reuse allocated memory. | You can reuse allocated memory after releasing memory using free() function. |
No library functions are required to allocate memory. | Requires Library functions like malloc(), calloc(), realloc() to allocate memory at runtime. |
We cannot modify the size of allocated memory. | We can modify the size of allocated memory using realloc(). |
Type of algorithmic problem solving
· A Static View of Algorithmic Problem Solving
Static program analysis is the art of reasoning about the behavior of the computer programs without actually running them. This is useful not only in optimizing compilers for producing efficient code but also for automatic error detection and other tools that can help programmers.
The halting problem asks whether the execution of a specific program for a given input will terminate.
The halting problem is famous for being undecidable.
That is, no algorithm can solve it for all programs and all inputs.
This complicates any attempt to predict program behavior: we can make predicting almost any program behavior equivalent to predicting the termination of a nearly identical program.
Static analyses are algorithms that do their best to defy the undesirability of the halting problem: they attempt to predict program behavior.
Predicting program behavior enables program optimization, security audits, automatic parallelization, and, if accurate enough, correctness verification.
· A Dynamic View of Algorithmic Problem Solving
These algorithms work by remembering the results of the past run and using them to find new results. In other words, a dynamic programming algorithm solves complex problems by breaking them into multiple simple sub-problems, and then it solves each of them once and then stores them for future use.
Fibonacci sequence is a good example for Dynamic Programming algorithms, you can see it working in the pseudo-code:
Fibonacci(N) = 0
(for n=0)= 0
(for n=1)= Fibonacci(N-1)+Fibonacci(N-2)
(for n>1)
Written by,
great !!
ReplyDeleteWow.. Really its very informative.
ReplyDeleteThank you.
nice explaination..
ReplyDelete