Computer Algorithm and its analysis

Computer Algorithm

What is a computer algorithm?

Computer algorithm is a step-by-step method for solving a problem by using a computer.

Actually, there are various strategies to solve a problem including, dynamic programming, randomized way, divide & conquer and many more.

In fact, there is no rule that you must use particular way to solve a problem. Every time you may find new way to do it. We can consider this way as a new algorithm.

Generally, how to solve a problem using a computer?

In fact, there is a problem to solve . You should find your strategy for what you will do next. You make some drafts until getting the clear idea. This idea becomes as an algorithm. I can say that algorithm is a structured idea for the solution.

The structure of algorithm consists of inputs, outputs and some steps. What does it mean? Let’s see a following problem:

Problem: Let E be an array containing n entries without any order. We have to find the index of K, if K is in the array. Otherwise, algorithm should return -1.

Strategy: Compare K to each element until a match is found or the array is exhausted. If nothing is found, return -1.

Input: E array, K key, n entries (indexed 0, 1, …, n-1).

Output: Returns answer, the location of K or -1.

Step is a code to explain computer to solve the problem. You may use any programming language for it. In this case, we write only its function:

int Search(int[] E, int n, int K){
int ans, index;
ans = -1; 			

for (index = 0; index < n; index++)
   if (K == E[index])
   {
        ans = index; 	
        break;
   }		
return ans;
}

After getting some experience with algorithms, you may move on the analysis. Here you pay attention to correctness, time & space, and optimality. By continuing the answer above, we measure the amount of work which has been done by an algorithm.

Let W(n) be an a function. It is the maximum number of operation that algorithm performs on any input size n. For the given example it is W(n) = n. The worst cases happen when K is found at the end of the array or not in the array. Best case is also possible, if the E is ordered array.

Leave a Reply

Your email address will not be published. Required fields are marked *