An Algorithm is a set of instructions to perform a task or to solve a given problem. For example, a recipe book is a collection of recipe in which each recipe provides a step by step instruction to prepare food. Let's say you want to prepare a tea. So, the steps would be -

Boil Water
Put tea in tea pot
Add hot water
Put hot tea into tea cups
Do you need sugar?
- If yes, put it into tea cups
- If no, do nothing
Stir, drink and enjoy!

Question: Print average of 3 numbers.

Let's say you want to write algorithm for it. So, the steps would be -

Perform sum of 3 numbers.
Store it in a variable sum.
Divide the sum by 3.
Store the value in variable avg.
Print the value stored in avg.

public void findAvg(int a, int b, int c) {
    int sum = a + b + c;
    int avg = sum / 3;
    System.out.println(avg);
}

Analysis of Algorithm

An Algorithm is a set of instructions to perform a task or to solve a given problem. There are several different algorithms to solve a given problem. Analysts of algorithm deals in finding best algorithm which runs fast and takes in less memory.

For Example -

Q. Find sum of first n natural numbers.

Input: n = 4

Output: 10 i.e., (1 + 2 + 3 + 4)
Input: n = 5

Output: 15 i.e., (1 + 2 + 3 + 4 + 5)

Let's consider we have two programmers A and B, who come up following algorithms,

public int sum(int n) {
    return n * (n+1)/2;
}

public int sum(int n) {
    int sum = 0;
    for(int i = 0; i <= n; i++) {
        sum = sum + i;
    }
    return sum;
}

So how do we decide which is the best algorithm? We can decide algorithm performance based on two factors:

Time Complexity
Space Complexity

Time Complexity

It's amount of time taken by algorithm to run. The input processed by an algorithm helps in determining the time complexity.

Space Complexity

It's amount of memory or space taken by algorithm to run. The memory required to process the input by an algorithm helps in determining the space complexity.

Asymptotic Analysis of an Algorithm

Asymptotic analysis helps in evaluating performance of an algorithm in terms of input sizes and its increase. Using asymptotic analysis we don't measure actual running time of algorithm. It helps in determining how time and space taken by algorithm increases with input sizes.

Asymptotic Notations

Asymptotic Notations are the mathematical tools used to describe the running time of an algorithm in terms of input size.

Example - Performance of car in 1 litre of petrol

Highway (min. traffic) - 25 km/litre
City (max. traffic) - 15 km/litre
City + Highway (avg. traffic) - 20 km/litre

Asymptotic Notations help us in determining -

Best Case
Average Case
Worst Case

Types of Asymptotic Notations

There are three notations for performing runtime analysis of an algorithm -

Omega (Ω) Notation
Big O (O) Notation
Theta (Θ) Notation

Omega (Ω) Notation

It is the formal way to express the lower bound of an algorithm's running time. Lower bound means for any given input this notation determines best amount of time an algorithm can take to complete.

For example - If we say certain algorithm takes 100 secs as best amount of time. So, 100 secs will be lower bound of that algorithm. The algorithm can take more than 100 secs but it will not take less than 100 secs.

Big (O) Notation

It is the formal way to express the upper bound of an algorithm running time. Upper bound means for any given input this notation determines longest amount of time an algorithm can take to complete.

For example - If we say certain algorithm takes 100 secs as longest amount of time. So, 100 secs will be upper bound of that algorithm. The algorithm can take less than 100 secs but it will not more than 100 secs.

Theta (Θ) Notation

It is the formal way to express both the upper and lower bound of an algorithm's running time. By lower and upper bound means for any given input this notation determines average amount of time an application can take to complete.

For example - If we run certain algorithm and it takes 100 secs for first run, 120 secs for second run, 110 secs for third run and so on. So, theta notations gives an average of running time of that algorithm.

Analysis of Time Complexity (Big O Notation)

Rules of Big O(O) Notation

It's a Single Processor
It performs Sequential Execution of Statements
Assignment operation takes 1 unit of time
Return statement takes in 1 unit of time
Arithmetical operation takes 1 unit of time
Logical operation takes 1 unit of time
Other small/single operations takes 1 unit of time
Drop lower order terms
Drop constant multipliers

Calculating Time Complexity of Constant Algorithm

public int sum(int x, int y) {
    int result = x + y;
    return result;
}

line no.	Operations	unit time
2	1 + 1 + 1 + 1	4
3	1 + 1	2

$$T = 4 + 2 = 6$$

$$ T \approx C (Constant)$$

public int get(int arr[], int i) {
    return arr[i];
}

$$Time\;Complexity = O(1)$$

Calculating Time Complexity of Linear Algorithm

public void findSum(int n) {
    int sum = 0; // 1 step
    for (int i = 1; i <= n; i++) {
        sum = sum + i; // n steps
    }
    return sum; // 1 step
}

line no.	operations	unit time
2	1	1
3	1 + 3n + 3 + 3n	6n + 4
4	n(1 + 1 + 1 + 1)	4n
6	1 + 1	2

$$T = 1 + 6n + 4n + 2$$

$$ T = 10n + 7$$

$$ T \approx n$$

$$ Time\;Complexity = O(n)$$

Calculating Time Complexity of Polynomial Algorithm

public void print(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            System.out.print("i= "+i+",j= "+j);
        }
        System.out.print("End of inner loop");
    }
    System.out.print("End of outer loop");
}

line no.	operations	unit time
2	1+3n+3+3n	6n+4
3	n(1+3n+3+3n)	6n^2+4n
4	n^2(1+1+1)	3n^2
6	n(1)	n
8	1	1

$$T = 6n + 4 + 6n^2 + 4n + 3n^2 + n + 1$$

$$ T = 9n^2 + 11n + 5$$

$$ T \approx n^2$$

$$ Time\; Complexity = O(n^2)$$

Algorithms and Analysis of Algorithms