Algorithms Introduction

Algorithms vs Program 

Algorithms are written at design time. It requires to have strong domain knowledge. It can be written any language or sudo code. No hardware requires and we should analyse the algorithms. Data type of input is not decided at algorithms time.

Program is written at implementation time. It requires to be a good programmer. It can be written in any programming language. Hardware and OS required. Program should be tested. Data type is decided at this point of time.

Characteristics of Algorithm

1. Input : May take 0 or more input

2. Output : Must provide some useful result

3. Definiteness : Every statement should be definite and clear

4. Finiteness : Algorithms must terminate at some point of time. That means duration of algorithms must be finite

5. Effectiveness : It should have effective statements.

Classes of functions

1. Constant time – O (1) 

2. Logarithmic time – O (log n) 

3.  Linear time – O (n)

4. Quadratic time – O (n^2) 

5. Cubic time – O (n^3)

6. Exponential time - O (2^n)

Comparison : 1 < log n < √n < n < n^2 < n^3 .... < n^k < 2^2 < 2^3 ...< 2^n ... < n^n

Asymptotic Notations

1. O : Big Oh - Upper bound

2. Ω : Big Omega. - Lower bound

3. Θ : Big Theta - Average bound

Priority is to represent Θ time complexity of given algorithms, if not then try to represent O.

Best, Worst & Average Cases