# What is Algorithms

- Algorithm
- Named after a Muslim mathematician,
*Al-**Khawarzmi*

* (*عَبْدَالله مُحَمَّد بِن مُوسَى اَلْخْوَارِزْمِي*)*

# What is an Algorithms ?

- Algorithm is a well defined computational procedure that takes some value (s) as input, and produces some value (s) as output.

**Algorithm Concepts**

**What is Data Structure? **

A data structure is a systematic way of organizing and accessing data. Some basic data structure as follows.

- Array
- Link List
- Stacks
- Queues
- Trees

**What is Program?**

Program is an implementation of an algorithm in some programming language.

**Data structure + Algorithm = Program**

**Design & Analysis of Algorithms**

1.**The “design” pertains to **

- i. The description of algorithm at an abstract level by means of a pseudo language, and
- Proof of correctness that is, the algorithm solves the given problem in all cases.
**The “analysis” deals with performance evaluation (complexity analysis).**

**Problem, Solution and Tools**

- A computer does not solve problems; it’s just a tool that I can use to implement my plan for solving the problem.
- A computer program is a set of instructions for a computer. These instructions describe the steps that the computer must follow to implement a plan.
- An algorithm is a plan for solving a problem.
- A person must design an algorithm.
- A person must translate an algorithm into a computer program.

**Algorithm Development Process **

**Good Algorithms?**

- Run in less time
- Consume less memory

But computational resources (time complexity) is usually more important

**Measuring Efficiency**

- The efficiency of an algorithm is a measure of the amount of resources consumed in solving a problem of size n.
- The resource we are most interested in is time
- We can use the same techniques we will present to analyze the consumption of other resources, such as memory space.
- It would seem that the most obvious way to measure the efficiency of an algorithm is to run it and measure how much processor time is needed
- But is it correct???

**Factors**

- Hardware
- Operating System
- Compiler
- Size of input
- Nature of Input
- Algorithm

Which should be improved?

**Running Time of an Algorithm**

- Depends upon
- Input Size
- Nature of Input
- Generally time grows with size of input, so running time of an algorithm is usually measured as function of input size.
- Running time is measured in terms of number of steps/primitive operations performed
- Independent from machine, OS

**Finding running time of an Algorithm / Analyzing an Algorithm**

- Running time is measured by number of steps/primitive operations performed
- Steps means elementary operation like
- ,+, *,<, =, A[i] etc
- We will measure number of steps taken in term of size of input

**Simple Example (1)**

// Input: int A[N], array of N integers

// Output: Sum of all numbers in array A

int Sum(int A[], int N)

{

int s=0;

for (int i=0; i< N; i++)

s = s + A[i];

return s;

}

How should we analyse this?

**Simple Example (2)**

1,2,8: Once

3,4,5,6,7: Once per each iteration

of for loop, N iteration

Total: 5N + 3

The *complexity function* of the

algorithm is : *f(N) = 5N +3*

**Simple Example (3)**

Growth of 5n+3

Growth of 5n+3

Estimated running time for different values of N:

N = 10 => 53 steps

N = 100 => 503 steps

N = 1,000 => 5003 steps

N = 1,000,000 => 5,000,003 steps

As N grows, the number of steps grow in *linear *proportion to N for this function *“Sum”*

**What Dominates in Previous Example?**

What about the +3 and 5 in 5N+3?

- As N gets large, the +3 becomes insignificant
- 5 is inaccurate, as different operations require varying amounts of time and also does not have any significant importance

What is fundamental is that the time is *linear *in N.

__Asymptotic Complexity__: As N gets large, concentrate on the

highest order term:

- Drop lower order terms such as +3
- Drop the constant coefficient of the highest order term i.e. N

**Asymptotic Complexity**

- The 5N+3 time bound is said to “grow asymptotically” like N
- This gives us an approximation of the complexity of the algorithm
- Ignores lots of (machine dependent) details, concentrate on the bigger picture

**Comparing Functions: Asymptotic Notation**

- Big Oh Notation: Upper bound
- Omega Notation: Lower bound
- Theta Notation: Tighter bound

**Big Oh ****Notation**

If f(N) and g(N) are two complexity functions, we say

f(N) = O(g(N))

*(read “f(N) is order g(N)”, or “f(N) is big-O of g(N)”)*

if there are constants c and N0 such that for N > N0,

f(N) ≤ c * g(N)

for all sufficiently large N.

- T(N) = 1000 N
- F(N) = N^2 is T(N)=O(F(N))?
- 1000N > N^2 for small values of N

Let N0 = 1000, c=1

Or N0 = 10, c=1000

1000N = O( N^2) at N= N0 = 1000

1000*1000 <= 1(1000)^2

- Compare the relative growth!
- T(N)= O(F(N)) or 1000N = O (N^2)

**Example (1)**

- Consider

f(n)=2n2+3

and g(n)=n2

Is f(n)=O(g(n))? i.e. Is 2n2+3 = O(n2)?

Proof:

2n2+3 ≤ c * n2

Assume N0 =1 and c=1?

Assume N0 =1 and c=2?

Assume N0 =1 and c=3?

- If true for one pair of N0 and c, then there exists infinite set of such pairs of N0 and c

**Big Oh Notation**

- T(N) = O(f(N)) means it is guaranteed that T(n) grows at rate no faster than f(N) so f(N) is “Upper bound” of T(n)
- N^3 grows faster than N^2 so we may say that N^2 = O(N^3)

**Example (2): Comparing Functions**

- Which function is better?

10 n2 Vs n3

- As inputs get larger, any algorithm of a smaller order will be more efficient than an algorithm of a larger order

**Big-Oh Notation**

- Even though it is correct to say “7n – 3 is O(n3)”, a better statement is “7n – 3 is O(n)”, that is, one should make the approximation as tight as possible
- Simple Rule:

Drop lower order terms and constant factors

7n-3 is O(n)

8n2log n + 5n2 + n is O(n2log n)

**Omega Notation**

If f(N) and g(N) are two complexity functions, we say

f(N) = **W**(g(N))

if there are constants c and N0 such that for N > N0,

f(N) >= c * g(N)

for all sufficiently large N.

**Small Omega Notation**

If f(N) and g(N) are two complexity functions, we say

f(N) = **W**(g(N))

if there are constants c and N0 such that for N > N0,

f(N) > c * g(N)

for all sufficiently large N.

**Theta Notation**

If f(N) and g(N) are two complexity functions, we say

f(N) = **Q**(g(N))

- c1 ´ f(n) is an
*Upper Bound*on g(n) *and*c2 ´ f(n) is a*Lower Bound*on g(n)

**Asymptotic notation**

- Example:
- f(n) = 3n5+n4 = Q(n5)

**Review of Three Common Sets**

**g(n) = O(f(n)) **means c ´ f(n) is an *Upper Bound* on g(n)

**g(n) = ****W****(f(n))** means c ´ f(n) is a *Lower Bound* on g(n)

**g(n) = ****Q****(f(n))** means c1 ´ f(n) is an *Upper Bound* on g(n)

*and *c2 ´ f(n) is a *Lower Bound* on g(n)

These bounds hold for all inputs beyond some threshold n0.

**Some Questions**

3n2 – 100n + 6 = O(n2)?

3n2 – 100n + 6 = O(n3)?

3n2 – 100n + 6 = O(n)?

3n2 – 100n + 6 = W(n2)?

3n2 – 100n + 6 = W(n3)?

3n2 – 100n + 6 = W(n)?

3n2 – 100n + 6 = **Q**(n2)?

3n2 – 100n + 6 = **Q**(n3)?

3n2 – 100n + 6 = **Q**(n)?

**Performance Classification**

**Size does matter[1]**

What happens if we double the input size N?

**Size does matter[2]**

- Suppose a program has run time O(n!) and the run time for

n = 10 is 1 second

For n = 12, the run time is 2 minutes

For n = 14, the run time is 6 hours

For n = 16, the run time is 2 months

For n = 18, the run time is 50 years

For n = 20, the run time is 200 centuries