Big Omega(Ω) Notation

Ω 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 n0 such that 0 ≤ cg(n) ≤ f(n) for all n… read more »

Dijkstra’s algorithm

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 and it works for directed as well as undirected graphs. The step by step process is specified below : Source vertex is chosen and marked. Mark distances at all… read more »

Big O Notation

  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… read more »

Time and Space Complexity

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… read more »

Pop operation in Stack

POP Operation 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… read more »

Push operation in Stack

Push Operation 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 possible. If  element is still  tried for insertion , OVERFLOW message will be printed on screen as the stack do not have extra… read more »

Binary Search

Binary Search 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. Program #include <stdio.h> int main() {… read more »

Kruskal’s Algorithm

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… read more »

Prim’s algorithm

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… read more »

Depth First Search in Graphs

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… read more »