In the design and analysis of an algorithm, we need to consider two-term Time complexity and Space complexity. without analyzing the time and space complexity we cannot analyze the performance of an algorithm and also cannot design the steps of an algorithm.

To design an algorithm we must consider the steps in a sequence so that it should have low time and space complexity.

Time complexity – Time complexity is used to estimate the running time of the algorithm in terms of the size of input data. for this purpose, we need to use a notation called big ‘O’ notation.

Space complexity – Space complexity is used to measure the defined extra space consumed by the algorithm except for input data. this is also considered in terms of input size and big ‘O’ notation is also used to measure the space complexity of an algorithm.

To calculate time and space complexity we use these notations.

1. Big Oh notation
2. Omega notation
3. Theta notation

The function f(n) = O(g(n)) (consider as “f of n is big oh of g of n”) if and only if there exist positive constants c and m such that f(n) =m.

The function 3n+2 = O(n) as 3n+2 =2

The function 6*2^n+(n*n) = O(2^n) as 6*2^n+(n*n) = 4.

so we can write O(1) to mean a computing time that is a constant. O(n) is linear, O(n*n) is called quadric, O(n*n*n) is called cubic and O(2*n) is called exponential. if there is an algorithm that takes time O(log N), it is considered to be faster than O(n).

The function f(n) = Ω(g(n)) (consider as “f of n is the omega of g of n”). if and only if there exist positive constants a and b such that f(n) >= a*g(n) for all n,n>=b.

The function 3n + 2 = Ω(n) as 3n+2 >= 3n for all n >= 1.

The function 6*(2^n)+(n*n) = Ω(2^n) as 6*2^n+(n*n) >= 6*(2^n) for all n >= 1.

The function f(n) = Θ(g(n)) (consider as “f of n is theta of g of n”). if and only if there exist positive constants c and m such that c*g(n) = 3n for all n>=1 and 3n+2 =2.

The function 6*(2^n)+(n*n) = Θ(2^n).

Counting the number of steps that are needed by a program to solve a particular problem has two ways. in the first approach we introduce a new variable, count into the program. this is a global variable that has initially a value of 0. so each time a statement is executed in the original program then this count is incremented by the step count of that statement.

Choosing an input to consider when analyzing an algorithm can have a significant impact on how an algorithm will perform. for example, if the input list is already sorted, some sorting algorithms will perform well, but on the other side, some may perform very poorly. also if we have a list that has randomly arranged instead of in a sporting manner. then there are some algorithms that perform well but others may not. hence we need to consider multiple input sets while analyzing the algorithm as given below.

Best case input – This case occurs when the input set allows an algorithm to perform in a very short time. with this input, the algorithm takes minimum time to execute. so, in this case, the algorithm needs to do the least amount of work to execute. let’s say we have a list of items and we need to find the item from a list. so the best case is if the item is available at the first position. so the algorithm needs to do the least work because the item is found in the very first position. so this is the best case for the algorithm.

Worst case input – This case occurs when the input set that we give to the algorithm takes a very long time to perform. it is a very useful case because using the worst-case analysis we can define the worst scenario of an algorithm. that gives us an idea of the long time that an algorithm takes to perform in every case. let’s say we have a list of items and we need to find out an item from that list. so what happens if the item is present at the last position of the list? so this is a worst-case scenario for an algorithm and it will take the most time to perform.

Average case input – This represents the input set that allows an algorithm to deliver average performance. doing average-case analysis is a four-step process. these steps are as under

the number of different groups into which all possible input sets can be divided is determined.

the probability that the input will come from each of these groups has been determined.

To design an algorithm we need to follow some rules to make an algorithm work and have low complexity. as we know an algorithm is a finite set of instructions to solve a particular problem. so to solve a particular task using an algorithm must need to satisfy the following criteria

1. Input – given by the user (this could be 0 or more)
2. Output – At least one output is produced by the algorithm
3. Definiteness – Each instruction is unambiguous and clear.
4. Finiteness – A algorithm always needs to terminate after a finite number of steps for every input.
5. Effectiveness – every instruction that we are using must always be in basic form so one can easily understand the meaning.

For an algorithm time, the duration for which the given input is generating the result, and the space it uses to store the steps are two major factors to measure the efficiency of an algorithm. the complexity of an algorithm is the function that gives the time and space complexity of that algorithm in terms of input size.

To represent the algorithm of a problem we have two parts in the first part we have a paragraph that tells the purpose of the algorithm that identifies the variables that occur in the algorithm. and the second part consists of the list of step that needs to execute.

For Assigning       set A = 1, LOC = 1 and MAX = A[1] (assign from left to right)

For comments        [comments that were never included in the program to execute]

All variables in the algorithm should be written in Capital letters

For assignment      =

Comparison          =, !=

For input           READ – Input variables

For Output           WRITE – Output variables

Let’s write some algorithms to understand the design of the algorithm.

Here in both examples, we have written the steps to get the sum of two numbers and find the maximum of two numbers. as we stated above in the first part we have to use the keywords to tell the purpose of the line just as Ready, Set, Write, Exit, If, and Else. and in the second part, we have included the steps that are to be executed.

1. Read – read the input data from the user
2. Set – Use the Assignments on the data
3. Write – print the data on the screen
4. Exit – exit from the program
5. If – check for the condition if true then execute a line
6. Else – If the conditions are false then execute a line
7. [End of If structure] – Comments for the users are always included in the [ ] parentheses.

Also, read

1. What is Data Structures and Algorithms
2. Classification of Algorithms
3. Evaluating and Expressing Algorithm
4. Complexity of Algorithm