Ω Notation provides the asymptotic lower bound on the function. A function needs to satisfy some conditions in order to be in Ω notation.Ω(g(n)) is the best case running time of function g(n) within a constant factor.

Ω(g(n)) = {f(n): there exist positive constants c and n_{0} such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n_{0}}.It is used to bound the best case running time of an algorithm.g(n) is an asymptotic lower bound for f(n).

Example 1

- Prove that if f(n) = 15n
^{3}+ n^{2}+ 4, then f(n) belongs to Ω(n^{3 }) for all n. - For omega notation,c*g(n) should be less than f(n).
- Here f(n) = 15n
^{3}+ n^{2}+ 1 - g(n) = n
^{3} - Let c=15
- 15 n
^{3}<= 15n^{3}+ n^{2}+ 1 _{n0 =1 }

- 15 n
- f(n) belongs to Ω class.
- Ω is the lower bound.

Example 2

- Show that 2n +7 is Ω(n) .
- f(n) = 2n + 7
- g(n) = 2n
- c * g(n) <= f(n)
- c*2n <=2n+7
- Let c=2
- 4n<=2n+7
- 2n<=7
- n<=7/2

- Thus for c=2 and n
_{0}= 7/2 f(n) belongs to Ω(n).

**Dijkstra’s** algorithm is way of finding **shortest path** from a **source** vertex to** sink** in a given **connected** and **weighted** graph.It is somewhat similar to Prim’s algorithm.It works for **directed** as well as **undirected** graphs.

**Source vertex**is chosen and**marked**.- Mark distances at all vertices as
**infinity**and at**source**vertex as**0**. - Update the distances of adjacent vertices from
**infinity**by given**distances**on the**graph**. - We look for
**minimum**distance value from source vertex to adjacent vertices. - The
**minimum distance**is chosen and next vertex is**marked**. - Look for the adjacent vertices of
**marked**vertex. - Replace the distance if it is less than the mentioned value at the vertices.
- Keep on following the same procedure until shortest path to sink is obtained.

**Example**

Consider a **weighted** and **undirected** graph as shown in Fig 1

- Choose a
**source vertex**.In Fig 2 ,**a**is chosen as the**source**vertex. **Mark**all the distances at vertices as**infinity**initially and distance of source vertex as**0**

- Look for
**neighbors**of source vertex a.(Fig 3). **b**and**i**are the**adjacent**vertices.- Update the
**distance**at**b**from infinity to**4**and at**i**to**8**. - Find the minimum distance from
**a**. **4**is smaller than**8**so**b**is the next**marked**vertex.

- Look for the
**neighbors**of b. **c**and**i**are the**adjacent**vertices.- Update value at
**c**from infinity to**12(4+8)**as distance from source to**c**is**12**.(Fig 4) - Distance from
**a**to**i**through**b**is**15**(11+4) and a to**i**directly is**8.**So**8**is not updated. - Look for next min distance to a vertex and do not count already marked vertices and edges.
- The distance at c is
**12**and at i is**8**,so**i**is marked.

- Look for neighbors of
**i**. - Update distance at
**h**to**15**(8+7) and at**g**to**9**. - Distance from source
**a**to**b**is**4**and**a**to**b**through**i**is**19**so it is not updated. - Look for next minimum distance from marked vertices.
**12,15,9**are the respective distances from marked vertices.- Mark vertex
**g**and**Edge(i,g)**as**9**is the minimum distance from source**a**to**g**through**i.**

- Look for neighbors of
**g**. - The distance at
**h**from a through**i**is**15**and from**a**through**i**and**g**is again**15**so it is not updated(Fig 6). - The distance from
**a**to**f**through**i**and**g**is**11**.So update it by**11**.

- Look for the next minimum distance(Fig 7).
**12,15,11**are the distances from marked vertices.- Mark
**f**and**Edge(g,f)**as distance is minimum.

- Neighbors of f are
**c,d,e**. - Distance at
**c**is not required to be updated. - Update distance at
**d**to**25**(11+14) and**a**t**e**to**21**(11+10)(Fig 8). - Look for minimum distance.
**12,15,19,21**are the distances available for consideration.- Mark vertex
**c**as**12**is minimum.

- Distance of neighbors of
**c**is not required to be updated. - Mark
**d**and then**e**.(Fig 9)

The following table gives the details of dijkstra’s algorithm applied on Fig 1.The shortest path from a to e is **{a,b,i,g,f,c,d,e}** with minimum cost of **21**.

- It gives
**rate of growth**of step count function**(f(n))**in terms of simple function**(g(n))**and defines the**asymptotic**upper bound on function(Fig 1). - To simplify the estimation for running time,
**constants**and**lower order terms**are ignored. - The function needs to satisfy following conditions in order to be in Big-O class.Given functions
**f(n) and g(n)**,we say**f(n)**is**O(g(n))**if and if**f(n) < c * g(n)**for all**n > n**_{0}- where
**c**and**n**are_{0 }**positive**constants.

- The function
**n**is does not belong to^{2 }**O(n)**rather it belongs to**O( n**as it fails to satisfy the inequality^{2 })**f(n)<=cg(n)**.**n**^{2 }cannot be less than**n**in any case as**c**is constant. -
**O(..)**is**worst case**(upper bound**) notation**for an algorithm’s**complexity**.

**Example 1**

- Consider T(n)=
**3n+2** **g(n) = n**- f(n) =
**3n+2** - We need to find first value of c where answer comes positive.Let
**c=1** - f(n)<=c * g(n)
- 3n+2 <= c *n
- 3n+2 <= 1*n
- The answer comes in
**negative**,so we cant choose c=1. - Let
**c=2** - 3n+2 <= 2n
^{ }The answer again comes in negative,so we cant choose c=2. **c=3**- 3n+2<=3n,can’t choose c=3
**c=4**- 3n+2<=4n
**n>=2****n**and_{0}=2**c=3**.This is the point where f(n) and g(n) meets.- Hence
**f(n)<=c*g(n)**and thus belongs to**big-O**class. - Highest power of n is 1.
- So
**f(n)**belongs to**O(n)**.

**Example 2**

- Consider T(n) =
**2n**^{2}+ 4 **g(n)=n**^{2 }- f(n) =
**2n**^{2}+ 4 - 2n
^{2}+ 4<=c *n^{2 } - The inequality is false for c=1 and c=2.
- c=3

2n^{2} + 4<=3 *n^{2 }

4<=n^{2 }

n=2 and n=-2,negative value is neglected.

**n>=2,n**_{0}=2 ,c=3- Thus
**f(n) belongs to O(n**.^{2 })

**Example 3**

- T(n) =
**3n**^{3}+20n^{2}+ 5 - 3n
^{3}+20n^{2}+ 5 <=c * n^{3 } - Is true for
**c=4**and**n**_{0 }= 21 - Thus
**3n**belongs to^{3}+20n^{2}+ 5**O(n**.^{3})

**Example 4**

- T(n) = 3 log n +5
- g(n) = log n
- f(n) = 3 log n +5
- f(n) <= c *g(n),
**c>0**and**n >****n**_{0} - 3 log n + 5 <=c * log n
**c =8**and**n**_{0 }= 2- Thus
**3n**belongs to^{3}+20n^{2}+ 5**O(n**^{3})

The various big 0 complexities are given in Fig 2 and Fig 3.

* *

Before defining the actual term complexity, let us discuss about few real life scenarios.Take an example of railway reservation counter.People go there to book their tickets.The time to book tickets will depend on how many service windows are available, queue size and time taken by each representative.A person will either go in a lane which is very short or will stand in queue where representative is very fast.Take another example of sitting plan of 40 students.The first thing to be considered is the no. of chairs needed and second thing is their order of sitting.If they sit roll.no wise then it will be easy for teacher to take attendance and time required will be lesser.Thus every process in the real world depends on how much** time** it takes to execute and how much space it consumes.**Complexity** is defined as the **running time** to execute a** process** and it depends on **space** as well as **time.**

It is of two types:

- Space Complexity
- Time Complexity

**Basic Operation**

Basic operation means the main operation that will be **required** to solve particular problem.For example the basic operation in searching is comparison.The complexity depends on the basic operation.

The focus to determine the **cost** is done on running time i.e** time complexity** and it depends on the following factors

- Size of Input Data
- Hardware
- Operating System
- Programming Language used

The amount of computer **memory** required to solve the given problem of particular **size** is called as **space** complexity.The space complexity depends on two components

**Fixed Part**– It is needed for instruction space i.e byte code.variable space,constants space etc.**Variable Part**– Instance of input and output data.**Space(S)**=**Fixed Part + Variable Part**

**Example 1**

*Algorithm sum(x,y)*

*{*

*return x+y;*

*}*

**Two computer words** will be required to store variable **x and y **so ,

**Space Complexity (S)= 2.**

**Example 2**

*Algorithm sum( a[], n)*

*{*

*sum =0;*

*for(i=0;i<=n;i++)*

*{*

*sum = sum + a[i];*

*return sum;*

*}*

Space complexity is calculated as follows

**One computer word**is required to store**n**.**n space**is required to store**array a[]**.**One space**for variable**sum**and**one**for**i**is required.**Total Space(S) =1 +n +1 +1=n+3**

The **time** required to **analyze** the given problem of particular** size** is known as the time complexity.It depends on two components

**Fixed Part**– Compile time**Variable Part**– Run time dependent on problem instance.Run time is considered usually and compile time is ignored.

- Use a
**stop watch**and time is obtained in**seconds or milliseconds**. **Step Count**- Count no of program steps.**Comments**are not evaluated so they are**not**considered as program**step**.- In
**while**loop**steps**are equal to the**number**of times loop gets**executed**. - In
**for**loop,steps are equal to number of times an**expression**is checked for**condition**. - A single expression is considered as a
**single**step.Example**a+f+r+w+w/q-d-f**is**one step**.

**Rate of Growth**(Asymptotic Notations)

**Example of step count**

*Algorithm sum( a[], 5)*

*{*

*sum =0;*

*for(i=0;i<=5;i++)*

*{*

*sum = sum + a[i];*

}

*return sum;*

*}*

Step count is a **difficult** approach if we need to **compare** results.For e.g.If we used two techniques to solve one problem and **T(1)** is the running time of first technique and **T(2)** is the running time of second technique.Say **T(1) =( n+1** **)**and **T(2)** is **(n ^{2 }+ 1)**.We cannot decide which one is the better solution,so for comparisons ‘

These notations gives the **rate of growth**.Instead of dealing with exact expressions we deal with asymptotic behavior.Asymptotic means to approach a value or curve arbitrarily closely.Focus is on the exponential behavior of equation.If we have expression like **T(n)=3n ^{3 }+5** and

- Big-O(O) – Refer Big O Notation
- Big-Theta(Ω)
- Big-Omega(Θ)

- Best Case
- Average Case
- Worst Case

It is the **minimum** time required to solve the given problem of particular size.For e.g.in **linear search** if element is found at first location then it will be the best case scenario and complexity will be **O(1)** as the running time is minimum.

It is **average** cost and time required for a given problem of particular size.For e.g. in** linear search** if there are n elements and item is found at n/2 location,then it will be a average case scenario and complexity will be **O(n/2)**.

The **maximum** time required to solve a given problem of particular size.For e.g in linear search the worst case will either be item is present at last location or it is not present.The complexity will be **O(n).**

In this operation **topmost element** is **deleted** from the stack.Before deleting check if **TOP = NULL**.If yes,it means that **stack is empty** and no deletion can be done.If an attempt to delete element is made in this case the **UNDERFLOW** message will be printed on screen.If no,then element is deleted then value of **TOP** is **decremented by** **1.**

**For example**

- We want to delete/
**pop 100**from this stack(Fig 9). **TOP = 4****TOP**is**not equal**to**null**.**100**is**popped out**/deleted.**TOP**variable gets**decremented**to**3**.

**Program 2**

#include<stdio.h>

int main() { int max; int stack[10]; int num,val,i,temp; int top = -1; //printf("Enter the maximum size of stack"); scanf("%d",&max); //printf("Enter the no of elements in stack"); scanf("%d",&num); //printf("Enter the elements of stack"); for(i=0;i<num;i++) { scanf("%d\n",&stack[i]); top++; } temp =top; if(top == -1) { printf("Underflow"); } else { top =top -1; printf("The stack after pop operation is \n"); for(i=0;i<temp;i++) { printf("%d\n",stack[i]); top++; } } return 0; }

- Refer
**Program 1**for working of**for loop**and consider the same values. **top = 4****temp = top**i.e**temp = 4****if( top ==-1)**i.e if no element is present in the stack then**Underflow message**will be printed on screen as no element is present to pop out.**top**= top -1 =4-1=**3**.**for(i=0;i<temp;i++)**-**i**would iterate till it is**less than temp(4).**- Elements of stack after pop operation is printed.

In this operation,the element is **inserted** at the **top of stack**(Fig 4).In order to insert element we need to check whether TOP = MAX-1.If yes,then insertion is **not possibl**e.If element is still tried for insertion , **OVERFLOW** message will be printed on screen as the stack **do not have extra space** to **handle new element**.If **space is present** and **element is inserted**,then the value of **top** will be **incremented by** 1 .

**For example**

- Say we want to insert/push
**800**in the following stack(Fig 4). **TOP = 4**(index starts from 0)**MAX= 13**- The value of
**TOP is 4**and**MAX-1 is 13-1=12.TOP**and**MAX**are**not equal,**thus element**800**can be pushed into the stack. - After insertion value of
**TOP**gets incremented t0**5**.

**Program 1**

#include<stdio.h> int main() { int stack[10]; int max; int num; int top = -1; int i; int item; //printf("Enter the maximum size of stack"); scanf("%d",&max); //printf("Enter the no of elements in stack"); scanf("%d",&num); //printf("Enter the elements of stack"); for(i=0;i<num;i++)//Fig 7 { scanf("%d\n",&stack[i]); top++; } if(top == max -1)//Fig 8 { printf("Overflow"); } else { //printf("Enter the item you want to insert\n"); scanf("%d",&item); top = top + 1;//Fig 6 stack[top] = item; printf("The stack after push operation is \n"); for(i=0;i<=num;i++) { printf("%d\n",stack[i]); top++; } } return 0; }

** Illustration of Program 1**

**Integer array**of**stack**with**size 10**is defined.**max**is the**maximum capacit**y of stack(Say 10).**num**is the**actual number**of elements in stack(Say 5).- Variable
**top**is initialized to**-1.** **i**is used in**for loop**and**item**is the element we want to push in stack.**for loop**(Fig 7) and**scan**f are used to read the values of stack.

The binary search technique works only on **sorted array**.It works by comparing the input element to the middle element of array.The comparison determines whether the element is less than.greater than or equal to middle element.Subsequent steps to be followed are written and explained by the following program.

#include <stdio.h> int main() { int val[10] = {10,20,30,40,50,55,68,77,89,90};//Fig 3 int beg = 0; //first index of array int end = 9; //end(last index of array) = n-1 where n is the size of array and is 10 in this case. int mid = (beg+end)/2; // finds middle index of array. int i; int element; //printf("enter the element you want search for"); scanf("%d",&element); for(i=0;i<10;i++) //Fig 4 { if(val[mid] == element) { break; } else if(val[mid] < element) { beg = mid +1; mid = (beg +end)/2; } else{ end =mid -1; mid = (beg +end)/2; } } printf("Location of element is %d",mid); return 0; }

**val[10]**of int type is initialized with values 10,20,30,40,50,55,68,77,89,90.**beg**variable of**int**type denotes the first index of array i.e.**0****end**variable of**int**type denotes the**last index**of array .It is equal to**(n-1)**,where n is the**size of array**.Here it is 10 so end=10-1=9**mid**index is calculated by adding beg plus end and the dividing the result by 2.**element**variable of**int**type is the data item which needs to be**searched**for in array and is entered by user using**scanf.**- Say we want to search for
**68**. - The following figure explains the working of
**for loop**to find 68.

**Kruskal’s** algorithm is a **greedy** technique used to find **minimum spanning tree** from the graph.It works on **edges** rather than on **vertices** in **connected weighted** graph.MST is obtained by finding global optimal choice.

**Technique**

**Mark**the**minimum weight edge**in the graph and**mark**the respective**vertices**.- Now,
**mark**the next minimum value in the graph. - If there are two or more
**edges**with same weight then select any**edge**at one time and then select others one by one. - We need to mark
**edges**according to the increasing**weight**of edges of different vertices. - Do not mark any edge on the graph which makes a
**cycle**. - Keep on repeating the process till
**MST**is obtained.

**Example**

Consider connected weighted graph in Fig 1.

- The
**minimum edge**weight on the graph is**1**.Edge**(Q,R)**and Edge**(S,W)**have same weight i.e**1**. - Choose any edge between them.
- Say we
**mark**Edge**(Q,R)**.(Fig 2) - Mark vertices
**Q and R**also.

- Now,
**mark**Edge**(S,W)**with weight**1**. **Mark**vertices**S and W**also.(Fig 3)

- Next min weight edge is
**2**. - Mark Edge
**(Q,P)**and vertex**P**.(Fig 4)

- The next min value in the graph is
**3**. - Mark Edge(
**R,S)**.(Fig 5)

- The next min value is
**4**. - Choose any edge between Edge
**(Q,T)**or Edge**(S,T)**. - Say we mark Edge
**(S,T)**with weight**4**. - The next value to be marked is
**4**but if we will mark Edge**(Q,T)**a**cycle SRQTS**will be formed. - So,do not mark this edge.
- We do not mark Edge
**(P,R)**with weight**5**,Edge**(T,W)**with weight**6**,Edge**(P,S)**with weight**13**for the same reason.(**Cycle formation**). - Now,mark Edge
**(W,X)**with weight**14**and mark vertex**X**.(Fig 6)

**Minimum spanning tree** is obtained as shown in Fig 7 and **cost** of minimum spanning tree is obtained by adding weights of all edges i.e **2+1+3+4+1+14=25**

**Prim’s** algorithm is a** greedy** algorithm as it finds the global** optimum** answer from collecting locally **optimum** choices.It finds the **minimum spanning tree** and works for **weighted,connected and undirected graph**.Minimum spanning tree is a graph is **edge weighted** graph whose weight is **smaller** than any other **spanning tree**.A minimum spanning tree is obtained by combining all local optimal choices to a global one.

**Technique**

- Put
**∞**as the**weight**at all**vertices**of the graph. - Write
**null**as the**parent**of each vertex. - Pick any
**vertex**from the graph. **Mark**it and replace the distance from**∞**to**0**.- Look for adjacent
**vertices**of**marked**vertex. - Replace
**∞**by given**weights**from the**marked**vertex to other vertices. - Replace parent
**null**by marked vertex name. - Choose minimum weight edge from the marked vertex.
**Mark**edge and another vertex .- Look for the
**adjacent**vertices. - If edge weight is smaller then replace the value as well by the
**parent**. - Now,look for all
**edges**from previous and newly marked vertex. - Choose the
**unvisited**vertex which is at**minimum**edge weight from marked vertices.(*Do not look again at marked vertices).* - Repeat the process till optimum solution is reached.
**Minimum spanning tree**is obtained as a result.

**Example**

Consider graph in Fig 1.

- Initially,put
**∞**followed by**null**and separated by comma at all**vertices**of graph.(Fig 2) -
**∞**is the weight and**null**is the parent

- Choose any
**vertex**from the graph. - Say
**T**is chosen. **Mark T**and replace weight by**0**.(Fig 3)- Add
**T**to the**set**i.e resulting sequence.

- Look for
**adjacent**vertices of T. **R,S,W**are the adjacent vertices.- Replace weights of
**R,S,W**by**12,4,6**respectively they are the distances from**T**. - Replace
**parent**of all**adjacent**vertices by**T**.(Fig 4)

- Choose the
**edge**from**T**which has**minimum**weight. **Edge(T,S)**is the shortest i.e**4**(compared to 12 and 6).- So mark the edge as well the vertex
**S**.(Fig 5). - Add
**S**to the set.

- Look for
**adjacent**neighbors of S. **P,R,W**are the adjacent vertices.- Replace value at
**P**by 1**3**and parent by**S**, as**13**is the edge weight from**S to P**. - Compare the edge weight betweenEdge(
**S, R**)and Edge(**T, R)**. **S to R**is**3**and**T to R**is**12**.3 is smaller than 12.- So,replace
**12**by**3**and**T**by**S**. - Compare weights between Edge (
**S , W)**and Edge (**T ,W)**. **S to W**is**1**and**T to W**is**6**.**1**is smaller so replace**6**,**T**by**1,S**.(Fig 6)

- Look for
**minimum**edge from**T and S**respectively. - 1 is minimum value(
**Edge(S,W)**). - Mark
**edge(S,W)**,vertex**W**and add them to the**set**.(Fig 7)

- Do not look for visited vertices again.
- Look for edges of
**T,S,W.** **3**is minimum edge value.**Mark edge**and vertex**R**.- Add
**R**to the set. - Look for
**unmarked**adjacent vertices of**R**. **P**is the unmarked vertex adjacent to**R**.- Replace
**13 by 5**and**S by R**as**5**is smaller than**13**.(Fig 8)

- The next
**minimum**value from edges of**T,S,W,R**is**5**. **Mark 5**and**P**.- Add
**P**to the set.(Fig 9)

- Replace value at
**Q**by**2**and parent by**P**.(Fig 10)

**Mark**2 and**vertex Q**.**Add Q**to the set.(Fig 11)

**Minimum spanning tree is **obtained and shown in Fig 12 and cost of minimum spanning tree is obtained by adding weights of all edges i.e.

**2+5+3+4+1 = 15**

** **

**DFS** technique is used to** traverse** graphs.Any **vertex** is chosen as the starting vertex .Element is pushed into stack.One adjacent vertex is randomly picked from adjacent vertices.It is **marked** and pushed it into stack.If adjacent unvisited neighbors are present then same process is followed otherwise element is popped off from the stack.Now,again one element is picked as the unvisited adjacent element and marked.Same process if followed till all the vertices are visited.

**Example**

Consider graph in Fig 1.We need to perform DFS on it.

- Pick any random
**vertex**.Say**A**. - Visit
**A**and mark it.(Fig 2) - Result Sequence–>
**A**

- Push A to the stack.(Fig 3)

- Find the
**neighbors**of A. **E,B,D**are neighbors of A.- Pick random vertex.Say
**B**. - Mark B.(Fig 4)
- Push
**B**to the stack.(Fig 5) - Result Sequence –>
**AB**

- Look for adjacent
**unvisited**neighbors of B. **C**is the neighbor.- Visit C and
**mark**it.(Fig 6) - Push
**C**to the stack.(Fig 7) - Result Sequence –>
**ABC**

- Look for
**neighbors**of C. **E and D**are neighbors.- Say we mark
**D**.(Fig 8) - Push
**D**to the stack.(Fig 9) - Result Sequence –>
**ABCD**

- Look for adjacent unvisited vertices of
**D**. - There are no adjacent unvisited vertices.
**Pop D**and look for adjacent vertices of C.**E**is the adjacent unvisited vertex.- Mark
**E**.(Fig 10) **Push E**to the stack.(Fig 11)

- Look for adjacent unvisited vertices of E.
**G and F**are the vertices.- Say
**G**is chosen. **Visit G**and mark it.(Fig 12)**Push G**to the stack.(Fig 13)

- Mark F and add to the stack(Fig 14,15)

- No other unvisited adjacent element of F is present.
- So,
**POP F**. - Same is the case with other vertices.
- So Pop all vertices one by one.