Algorithms and the Need For Analysis In Programming languages

Understand the concepts of computer science

Introduction

Algorithms play an essential role in understanding the concepts of computer science. Mostly we learn by seeing others solve the problem and then by trying to solve it on our own. The algorithm helps us understand the task at our hand better by breaking them into a finite number of steps and arranging them in the required order.

Hence, the algorithm combines sequences of a finite number of steps to solve a problem. Infinite steps would take endless time, giving us no proper solution, and thus it should always be a limited number of steps.

Along with the finiteness, there are some more aspects that one must keep in mind while writing an algorithm.

Properties of Algorithm

It should terminate within a finite time. It is crucial to remember that finite steps do not always imply finite time. Forex: while (1)

print(“hi”)

Even though it consists of just two steps, it will get into an infinite loop, taking endless time.

Every statement in an algorithm should be effective (i.e., each statement is supposed to do some work)
It should be deterministic, which means determining a proper solution and not being ambiguous.
It should have zero or more well-defined inputs.
It should have one or more well-defined outputs that match the required output.
It should be a step-by-step direction of solving a problem independent of any programming language.

Hence, to check if some written sequence is an algorithm or not, one must consider all these points and conclude accordingly.

Steps To Design an Algorithm

As said earlier, the algorithm helps break down the problem, making it easier for us to solve a problem, and thus it is essential to keep the following points in mind while designing an algorithm for a problem.

It is important to identify the problem statement.

Talking in terms of programming, the output should be clear to you for every input.

Selection of a proper design technique for the algorithm.

For algorithms, there are already available techniques like Divide and Conquer, Greedy, Dynamic Programming, etc. One needs to select the appropriate and effective one and apply it to the required problem.

Draw a flowchart to get a clear view.
Verification and testing of the algorithm for the given problem.

One needs to understand that the algorithm is the best if, for every input, one gets the correct output while verifying. Depending on the result, one may need to re-design the algorithm in this phase.

Analyzing the time and space complexity of the resultant algorithm.

A critical step in designing the algorithm is analyzing the algorithm.

Why is Analysis Important?

To solve problem P, there may be more than one algorithm possible, and hence there is a need for analysis to choose the better algorithm for the problem. Even though the aim of all available algorithms for a problem is the same, they are usually different from one another. Like, there are many sorting algorithms available, but their complexities differ. Analysis of algorithm is the process to examine the problem-solving capacity of an algorithm in terms of time and memory space required.

Analysis of algorithm can be broadly classified into two categories:

Posteriori Analysis

According to this kind of analysis, the time complexity of an algorithm is dependent on the language of the compiler and the type of hardware. Posteriori Analysis is like a hands-on experimental analysis of an algorithm. The algorithm is implemented using programming language and then executed on the target system giving us the exact answer for the running time and the space required. Although this analysis provides us with an accurate solution, the complexity keeps changing from machine to machine and is thus not very practical to use. The credit for the program taking less time to run goes to the compiler and the system’s hardware, in this case.

2. Priori Analysis

According to this kind of analysis, the time complexity of an algorithm is independent of the language of the compiler and the type of hardware used in the system. Priori Analysis is basically about the theoretical analysis of an algorithm where the algorithm’s efficiency is measured by assuming that factors like processor speed are constant and have no effect on the implementation. It gives us an approximate answer but is the same for all systems. It uses the asymptotic notations (will be discussed next) to represent how much time and space will be used by the algorithm to complete its execution. Here, the credit goes to the design of the algorithm if the programs run faster.

While analyzing an algorithm, 3 cases may arise specific to an algorithm. The best-case implies the minimum execution time, while the worst-case implies the maximum execution time. The average case says the behavior of an algorithm in an average situation.

For example, Quick Sort requires maximum time when the input list is sorted in either ascending or descending order. Its performance is the best when its elements are in random order. Its average case corresponds to when fewer or more elements are out of place for their actual positions in the list if it was in sorted order.

Python Data Structures Data-types and Objects

Handy concepts on class objects in python

pub.towardsai.net

Understand List as Big O and Comprehension with Python Examples

The list is a part of python data structures

pub.towardsai.net

What is Asymptotic Notation?

Asymptotic Notation is used to express the running time of an algorithm, i.e., the time taken by the algorithm to run for a given input, n. There are three kinds of asymptotic notation as follows:

Big-O Notation:

This notation Ο(n) is used to express the upper bound of the running time of an algorithm, i.e., it gives us the time or space taken by the algorithm in the worst-case scenario. It says that for a function f(n),

O (g(n)) = {f(n): there exist positive constants c and n0 such that f(n) ≤ c*g(n) for all n ≥ n0}

This means that f(n) = O(g(n)), If there are positive constants n0 and c such that, to the right of n0 the f(n) always lies on or below c*g(n).

2. Omega Notation:

This notation Ω(n) is used to express the lower bound of the running time of an algorithm, i.e., it gives us the time or space taken by the algorithm in the best-case scenario. It says that for a function f(n),

Ω (g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ c*g(n) ≤ f(n) for all n ≥ n0}

This means that f(n) = Ω(g(n)), If there are positive constants n0 and c such that, to the right of n0 the f(n) always lies on or above c*g(n).

3. Theta Notation:

This notation θ(n) is used to express both the lower bound and the upper bound of the running time of an algorithm. It says that for a function f(n),

Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1*g(n) ≤ f(n) ≤ c2*g(n) for all n ≥ n0}

The above equation is a function of (n) in which the positive constant n0 and c lie between the c1 and c2.

Let us understand this better using the example of an Insertion Sort.

Insertion Sort is an important technique of arranging the elements in order. It is based on the principle of inserting the elements in the required position.

An example to illustrate Insertion Sort technique is as follows:

#Let us consider an array 
array = [8,2,4,9,3,6]

Pseudocode for Insertion Sort:

for i = 1 to length(array)
    key_indexes = array[i]
    j = i-1
    while j >= 0 and array[j] > key_indexes
        array[j+1] = Aarrayj]
        j = j-1
    endwhile
    array[j+1] = key_indexes
endfor

Analysis of Insertion Sort

Best-case:

When the array elements are in ascending order and you need the array to be sorted in ascending order, it is considered as the best-case scenario. In this case, insertion sort performs O(n) comparisons and no swaps. Thus, the best-case time complexity is O(n).

Worst and Average case:

When the array elements are in descending order and you need the array to be sorted in ascending order, it is considered as the worst-case scenario. In this case, insertion sort performs at most n-1 comparisons and n-1 swaps to insert the last element in its correct position, at most n-2 comparisons and n-2 swaps to insert the second last element in its correct position, and so on. Finding the summation and solving it using

In recurrence relation, we get the worst-case time complexity to be O(n²).

The average-case time complexity for insertion sort is the same as the worst-case time complexity and is O(n²).

Space Complexity:

Talking about space complexity insertion sort is a stable sort with space complexity of O (1).

Python Implementation of Insertion Sort:

I hope you like the article. Reach me on my LinkedIn and twitter.