Analysis Of Algorithms

Analysis Of Algorithms

Outline:

• Analysis of an algorithm
• Time complexity
• Types of time functions/Order of algorithm
• Space complexity

In this lesson, you will learn about the theoretical aspect of the algorithms. In the previous lesson, you have learnt about algorithms.

Whenever you design an algorithm, you should keep in mind these two parameters that are time and space. How much time it takes to execute the algorithm, how much time it is taken by an algorithm. Whereas space complexity means how much space or memory is required for variables and instructions used in this algorithm. Time complexity and space complexity are the two most important parameters to analyse the efficiency of an algorithm and these should be independent of the machine.

As I discussed earlier often several different algorithms are available for a single problem. Sometimes it becomes a complicated task to select the best algorithm in terms of time and space.

Time Complexity:

Time complexity is defined as the amount of time taken by the algorithm. It is written as a function of the length or size of input n. It describes the efficiency of the algorithm in terms of a number of operations. As the number of operations or instructions increases, the computational time increases as well (of course!!). Generally, the lesser number of operations, the faster will be the algorithm. In this section, I am going to explain which algorithm is faster than the other. I am going to derive mathematical expressions for different algorithms.

Note:

Time complexity determines the worst-case run time.  This will explain in detail in later lessons.

Example 1:

Take algorithm for adding two numbers.

Start

Declare variables: num1, num2, result

Result = num1 + num2

Display result

Stop

Count the number of operations the computer should perform.

The total number of steps/operations = 3

Time is taken by each step = 1  unit of time

Time is taken by all step = 3  units of time

Time complexity = O(3)

Where O(3) stands for the order of 3. This will explain in details in the upcoming lecture.

I assume each step takes one unit of time to execute. In real applications, this is not happening. In computing, every statement takes a different amount of time to execute. Execution time also depends on many other factors as well.

Evaluate Time Complexity (Examples) | Order Of Algorithm| Types of Time Function and Order of growth:

We write time complexity like this O(n). This is called a big O notation. This is an asymptotic notation. We will discuss this in the upcoming lecture. The common time complexity functions and their examples are given below.

Constant: (any constant number)

Example is a statement that is simply adding two numbers. I have discussed the algorithm for adding two numbers. It is an example of constant time function

Linear: N

An example is a single loop.

Example 1: Let's take an algorithm for 'for loop’.

Start

For numbers 0 to n

Print “hello world”

End

Another way of writing the similar algorithm

Start

For (i = 0, i<n, i++)...... 'n+1’ times

Print “hello world” ……'n’ times

End

Both algorithms are the same, having the same number of instructions or operations. The second algorithm uses for loop syntax. Actually for loop is a high level programming language construct (part of programming language. Syntax may vary from one language to another). So, for loop remains the same in any programming language.

Let's begin. How many steps/ operations or instructions in the above algorithm?

For loop iterates for 'n+1’ times. Print statement repeats 'n’ times.

The total number of steps/operations = n+1

Time taken by every step = n+1 units of time

Time complexity = O(n)

I omitted +1 because it is a constant and order remains the same. It means this algorithm process the input in n units of time.

Example 2: Let's take an algorithm for 'while loop’.

We want to investigate how many times the loop iterates. And hence the time taken by the program.

Start

Declare variables i = 0, n ... executes 1 time

While ( i < n )  ….. executes 'n+1’ times

Print “hello world”. …. executes ‘n’

i++    …. executes ‘n’

End

The total number of steps/operations = 3n+2

Time taken by all steps = 3n+2 units of time

Time complexity = O(n)

Logarithmic: log N

Example is binary search (divide in half). Here for/while loop has logarithmic iterations.

Example 1:

Start

Declare variables i,n ….. executes 1 time

For (i = 1, i<n, i = i*2) ….

Print “hello world”…..executes log2 (n) times

End

I draw a table. With the help of this table you can understand how does the loop repeat and how does value of 'i’ change?

i	i < n	i = i*2	Explanation
i = 1	i < n	i = 1*2 = 2	Simple multiplication
i = 2	i < n	i = 2*2 =4	In each iteration variable i is multiplied by 2
i = 4	i < n	i = 4*2 = 8 i = 22*2	We can generalize i = 22*2
i = 8 = 23	i < n	i = 8*2 = 16 i = 23*2
i = 16 = 24	i < n	i = 16*2 i = 24*2
i = k = 2k	2k < n	i = k*2 i = 2k*2	Suppose the loop repeats itself 'k’ times. We got a general term.

We can write 2k <= n

Apply log on both sides.

k = log2 (n)

The loop iterates log2 (n) times.

The total number of steps/operations = log2 (n)

Time taken by all steps = log2 (n) units of time

Time complexity = O(log2 (n))

Note: most of the time you get fractional values. But you will take the whole value. Round off the result, you will get the actual value

Example 2:

Start

Declare variables i = 0, n ... executes 1 time

While ( i < n )

Print “hello world”…. executes log2 (n) times

i = i*2    …. executes log2 (n) times

End

All calculations are the same for both loops.

The total number of steps/operations = log2 (n)

Time taken by all stepss = log2 (n) units of time

Time complexity = O(log2 (n))

Quadratic: N2

Example is double (nested) loops.

Now again we use algorithm for ‘for loop’. It means loop within a loop. There is an example for nested loops. Consider 10 boxes, in each box there are 10 balls. How do you count them.

• First you count the total number of boxes
• Open each box and count the number of each box
• Each box contains 10 balls.
• 10 boxes contain 10*10 balls

Same strategy is applied for nested loops.  In other words you can say that there are two linear nested functions

Start

For (i = 0, i<n, i++)...... 'n+1’ times

For (j = 0, j<i, j++) ……’n’ times

Print “hello world” ……'n*n’ times

End

The total number of steps/operations = (n+1)*n

Time taken by all steps = (n+1)*n units of time

f(n) = (n+1)*n

O(n) = n2

Space Complexity:

Space complexity is also a measure of efficiency of an algorithm in terms of memory. An algorithm is efficient if it occupies less memory than the other.

S(p) = C + Sp

Where

S(p) = space requirements

C = constant, it is the space taken up by variables and instructions.

Sp = space characteristics, it is a variable part. Space dependent upon instance characteristics. It varies from one algorithm to the other.

1. To analyse an algorithm there are two important parameters

1. One
2. Two
3. Three

2. Time complexity means the amount of time taken by an algorithm or it defines efficiency of algorithm.

1. True
2. False

3. Space complexity determines the efficiency of algorithm in terms of space

1. Space
2. Area
3. Length
4. None

4. The example of quadratic time function is double loops.

1. Single loop
2. Nested loops
3. Double loops
4. None

5. Single loop is an example of linear time function

1. Cubic
2. Quadratic
3. Linear
4. Non linear

6. The formula for space complexity is S(p) = C + Sp

1. True
2. False

7. Time complexity for the function below is

Start

For (i = 0, i<n, i+2)

Print “hello world”

End

1. Linear
2. Quadratec
3. Cubic 

Introduction To Algorithms:

Outline:

• What is an algorithm with examples
• Properties
• Representation
• Pseudocode
• Flowcharts
• Examples

An algorithm is a term commonly used in computer science and mathematics. It is a 'problem-solving method’.  You must be familiar with this term. It is the finite set of instructions, logic and step by step procedure execute in a finite amount of time. You can assume it as a to-do list for programmers.

Understand the meaning of the above definition.

A finite set of instructions: there should be a limited number of instructions

Logic: there should be logic, how to solve a particular problem.

Step by step: it consists of a few steps to follow while writing the actual code.

A finite amount of time: It has a finite number of instructions that have to be performed in a finite amount of time.

It is independent of the programming language. It is also called a procedure. The computer can not understand instructions written for human beings. It tells a human being what steps should take to perform a specific task or solve a problem. These steps should write sequentially. Some points to keep in mind while writing an algorithm are:

• There is no specific format or well-defined standard or fix syntax or language
• When writing an algorithm for a computer program, we can use code constructs which are common in all programming language like loops, flow control, variable declaration etc.

Example: School Routine

Algorithms are not limited to computing or mathematics. They can be applied to our daily lives. Let's check out this example.

When a kid goes to school, he follows these steps.

• Wake up early in the morning
• Brush his teeth and take a bath
• Wear uniform
• Have breakfast
• Get ready for school
• Go to the bus stand
• Wait for the transportation
• Get the bus
• Go to school

Properties/Characteristics:

An algorithm has the following properties.

Input:

There should be input.

Output:

There must be output as well. Otherwise, the algorithm is useless.

Finiteness:

It should terminate after a finite number of steps.

Determinacy:

Each step should clear, precise and unambiguous.

Effectiveness:

Each step of an algorithm executes effectively.

Generality:

It is equally applicable to all types of inputs. If the input changes the output changes accordingly.

Why do we need algorithms:

When you are writing a computer program, the first step is to write an algorithm. It is independent of the programming language. The purpose of an algorithm is to clearly express what you want to do. The steps which has to follow while solving the problem. In programming, the algorithm is a part of a programmer's job. It is his task to translate an algorithm successfully into a program.

Algorithms are also useful in analyzing computational resources like time to run a program that is computational time, space allocated by a program or memory management, etc.

Representation:

An algorithm can be represented either in pseudocode or flowcharts. Both techniques are used by coders, programmers and designers.

What is pseudocode? How to write an algorithm using pseudocode?

Pseudocode is an arbitrary language for describing algorithms. It only focuses on logic irrespective of the programming language. The purpose is to convey the problem-solving method as a text outline. It can easily be understood by a non-programmer as well. Ideally, pseudocode does not contain syntax and keywords.

What is a flowchart? How to write an algorithm using a flowchart?

A flowchart is the graphical representation of an algorithm. It consists of different geometrical shapes that describe the flow of a program. It describes the sequence of steps with the help of geometrical shapes involved in a problem. Directed arrows show the flow of the program.

Example 1: A simple program

Addition of two numbers

x = y+z

Pseudocode:

Start

Declare variables: num1, num2, result

Result = num1 + num2

Display result

Stop

Explanation:

In the first step, declare three variables. You need to add two numbers and then store the result in the third variable.

In the second step, the actual task that is addition is performed. This task is performed internally. If you need to display the results you have to write another instruction.

In the third step, there is an instruction for displaying the result or output.

Check the algorithm, it has all the properties that are stated above. Like input, output, finiteness (only three instructions), effectiveness, determinacy and generality.

Flowchart:

Explanation:

This is another way! A pictorial representation. Have a look at it. All the steps are the same. Different shapes show indicate that which is an input/output. Parallelograms show the input and output of the program. The rectangle shows the processing that is the task. Here addition is performed.

Example 2: Algorithm for control flow statements

Find the largest among three different numbers entered by the user

Pseudocode

Start

Declare three variables a, b, c

Read variables a, b, c

Compare variables using a conditional statement

If (a>b && a>c)

   Display 'a’ is the greatest among three numbers

Else if (b>a && b>c)

      Display 'b’ is the greatest among three  numbers

Else

      Display 'c’ is the greatest among three numbers

End

Explanation:

In the first step declare three variables.

In the second step, I write the 'read’ command. It means you ask the user to enter variables. After the user enters these variables, the system will read them.

In the third step, there is a decision making statement. Check if a is greater than or not. If a is greater than b then proceed further. Check whether a is greater than c as well. If this condition is also true, then proceed further.

Flowchart

Explanation:

In the first step, the processing box is there for the declaration of three variables

In the second step, the input/output box is there for input.

In the third step, a rhombus (labelled as a>b) is there. It means some decision making task. It compares two variables at a time.

The same comparison process in the next step.

In the last step again parallelograms are there to display the results/ outputs

Example 3: Algorithm for iterative statements (condition controlled statement do-while loop)

Print number 1 to 5

Pseudocode

Start

Declare and define variable Count = 1

Do

 Display count

 Count = count+1

While count <6

End

Explanation:

In the first step, a variable is declared and defined.

In the second step, a loop begins. A do-while loop.

In the third step, an instruction ‘ Display count’ is there.

The third step repeats until the condition is not satisfied.

In the fourth step, the count variable is incremented by 1.

In the fifth step, the condition is there. How many times does the loop repeat itself? The loop repeats until the variable count becomes 5.

So, the loop iterates 5 times and display the value of count each time.

Flowchart

Important terms:

Condition controlled loops: do-while loop is a condition controlled loop. Its iterations are based on specific conditions. It repeatedly checks whether the condition met or not.

Control flow statements: looping, decision making, branching statements are control flow statements.

Iterative statements: as the name implies it is a repetitive process. for loop is an iterative statement.

Syntax: in simple words, you can say it is the grammar of a programming language. It is a set of rules that specify the correct sequence of words and phrases.

&& (AND AND condition): it is also called logical AND operator. It returns a Boolean value that is either true or false.

Multiple Choice Questions

1. Algorithm is defined as a finite set of instructions executed in a finite amount of time.

1. A finite amount of time
2. 10 minutes
3. Infinite amount of time

2. Algorithm is independent of programming language, so it has no fixed syntax.

1. A fixed syntax
2. No fixed syntax

3. Generality of the algorithm means it is valid for various set of inputs. If input changes, the output changes accordingly.

1. True
2. False

4. Algorithms are helpful in analyzing computational time.

1. Wind speed
2. Computational time
3. None

5. When you are going to write a computer program, the first step is to write its algorithm.

1. Algorithm
2. Code
3. Name
4. None

6. Algorithms can be represented by pseudocode or flowcharts.

1. True
2. False

7. A single problem has plenty of algorithms.

1. One
2. Two
3. Many
4. Plenty
5. c and d

8. Pseudocode is written in a high-level programming language

1. True
2. False