Operation time complexity for an ARRAY

The time complexity of handling the operations in a data structure like an ARRAY are as follows:i. Almost all the operations are O(1) [i.e. omega times one]ii. Remove/Insert operations that handles element between elements require O(n) [i.e. omega times n] because the elements need to be shifted.Note! Hence, an array as a data structure is used where remove/insert operations are not required...

Read More

Operation time complexity for a LINKED LIST

The time complexity of handling the operations in a data structure like a LINKED LIST are as follows:i. Most of the operations are O(n) [i.e. omega times n]ii. Remove/Insert operations that handles element between elements require O(1) [i.e. omega times one] this is due to references/pointers on both the ends of the list, hence the elements don't require to be shifted. However, due to the references/pointers this data structure requires additional memory...

Read More

Time complexity - Omega of algorithms

a) if statement - O(n) [Omega times n] b) for loop - O(n) [Omega times n] c) for loop with a for loop - O(n*n) [Omega times n squared] d) for loop within a if loop, this if loop is within a for loop - O(n + n*n) [n plus n squared omega] e) while loop - O(n) [Omega times n] f) MergeSort - O(nlogn) [Omega n time logarithmic n] g) HeapSort - O(nlogn) [Omega n time logarithmic n] h) KMP algorithm - O(m+n) [m plus n omega...

Read More

Time complexity of algorithms - In particular Big Omega of algorithms

Big Omega or so called asymptotic upper bound of algorithms such as Sequential statements, If statements and Looping construct(i) Sequential statements:Big Omega of this algorithm equals to maximum time complexities of all individual statements (i.e. sum of maximum time complexities of the individual statements)Therefore, O[g(n)] = O{f1(n)+f2(n)+ ... +fk(n)}Conclusion: Overall complexity of this algorithm equates to O[g(n)](ii) If statements:Big Omega of this algorithm equals to maximum time complexities of either one of the alternative statements...

Read More

String Searching Algorithm - Knuth Morris Pratt or KMP Algorithm

Knuth-Morris-Pratt string searching algorithm: - This algorithm searches a word->w within the main string text->s - Such a search must employ the following observation: i) A given match determines where the next match could begin ii) The above intelligence is obtained for the search word itself that contains sufficient information for making such a discussion (i.e. determine where the next match begins) Advantage of this string searching...

Read More

Priority Queue

What is priority queue? A data structure for maintaining items or elements in a queue of priorities, which is usually implemented using an array. A queue of this nature helps to insert every item with an assigned priority and these inserted items could be deleted if required. Minimum number of queues needed to implement the priority queue? Two. One queue is used for actual storing of data and another for storing priorities. With priority queue it's possible to insert items then remove max or min. Simple implementation is to have array...

Read More

What is a non-linear datastructure?

A non-linear datastrucutre is a datastructure in which the data items in the memory are not allocated contiguously i.e. the data items are dispersed in the memory. The first data item will have a link to the second data item and second data item will have a link to the third data item and so on.Pros Uses memory efficiently that the free contiguous memory in not an requirement for allocating data items The length of the data items is not necessary to be known prior to allocation Cons Overhead of the link to the next data item Examples of...

Read More

What is a linear datastructure?

Linear datastructure is one in which the data items are placed in the memory contiguously i.e. one after the other.Pros If we search the first data item, then it is very easy to find the next data items Cons Size of the array must be know prior to allocation Requires contiguous memory, however if a free memory space is disjoint then this free memory space is not utilized for memory allocation Example of linear datastructure is an array...

Read More

What is a sorting algorithm?

A sorting algorithm is an algorithm that sorts the data into ascending or descending order. Examples of such sorting algorithms are: Radix sorting Heap sorting Selection sorting Bubble sorting...

Read More

Insertion sort

The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. Insertion sort: An efficient elementary sort method which places each element in it's proper place among the elements which are already placed Pseudocode for selection sort Starts by considering the first two elements of the array data, if out of order, swap them  Consider the third element,...

Read More

Introduction to Heap

Definition of a heap A heap is a data structure that contains objects which have comparable keys. Uses of Heap Some uses for a heap include: keeping track of employee records where the social security number is the key, network edges, events where there is a priority, etc. Such a heap is called descending heap. In an ascending heap, on the other hand, the key value stored in a node is smaller than the keys of its children nodes. Heap ADT...

Read More

Selection Sort

The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. Selection Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of in-place comparison sort. Pseudocode of selection sort Get the smallest element and put it in the first position Get the next smallest element and put it in the 2nd position .... Sorting ...

Read More

What is Bucket Sort?

Bucket Sort (alternatively know as bin sort) is an algorithm that sorts numbers and comes under the category of distribution sort. This sorting algorithm doesn't compare the numbers but distributes them, it works as follows: Partition a given array into a number of buckets One-by-one the numbers in the array are placed in the designated bucket Now, only sort the bucket that bare numbers by recursively applying this Bucket Sorting algorithm Now, visiting the buckets in order, the numbers should be sorted Java code: public class BucketSort{ ...

Read More

What is a Graph data structure?

Graphs consist of 2 ingredients : Vertices (V) , also called nodes and can be pictured as dots Edges (E) , the line connecting the nodes. Types of Graphs Depending on the edges, there two types of graphs: Undirected Graphs - A graph that entail edges with ordered pair of vertices, however it does not have direction define. Example of such a graph is the 'Family tree of the Greek gods' Directed Graphs (aka Arcs) - Directed Graph: A graph that...

Read More

Graph Traversal Methods

There are two possible traversal methods for a graph: i. Breadth-First Traversal ii. Depth-First Traversal i. Breadth-First Traversal: Traverse all the vertices starting from a given 'start vertex'. Hence, such a traversal follows the 'neighbour-first' principle by considering the following: - No vertex is visited more than once - Only those vertices that can be reached are visited Importantly here, we make use of the Queue data structure. In effect, we house the vertices in the queue that are to be visited soon in the order which they are...

Read More

Find shortest path using Dijkstra's Algorithm

The Dijkstra's algorithm entails the following procedure: - The breadth-first approach is used to traversal the network, however the difference here is instead of a queue data structure to store the traversed vertex this algorithm uses a priority queue. The priority queue helps to remove the items in order of values rather than in order of being added to the queue. - Have an account of lowest total path weight (i.e. weightsum), from the start vertex to the target vertex - Have an account of immediate predecessor in a given path for each vertex -...

Read More

Hashing, Hash Data Structure and Hash Table

Hashing is the process of mapping large amount of data item to a smaller table with the help of a hashing function. The essence of hashing is to facilitate the next level searching method when compared with the linear or binary search. The advantage of this searching method is its efficiency to hand vast amount of data items in a given collection (i.e. collection size).Due to this hashing process, the result is a Hash data structure that can store or retrieve data items in an average time disregard to the collection size.Hash Table is the result...

Read More

What is a Complete Binary Tree?

A strictly binary tree of depth 'd' in which all the leaves are at level 'd' i.e. there is non empty left or right subtrees and leaves are populated at the same level.In a complete binary tree all the internal nodes have equal degree, which means that one node at the root level, two nodes at level 2, four nodes at level 3, eight nodes at level 4, etc, which the below figure represents: ...

Read More

Binary tree traversal: Preorder, Inorder, Post-order, BFS, DFS, Level Order, zig zag order

In order to illustrate the 3 traversals  - pre order, in-order and post-order lets take following tree: Preorder traversal: To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree. Therefore, the Preorder traversal of the above tree will outputs: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10 Implementing pre-order traversal preorder(N *root) { ...

Read More

Data Structure Introduction

The basic building block of DATA STRUCTURE are "data" and "information". So, before discussing data structure, we need to understand what is data and some ground facts about data structure. Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4 ...

Read More