Master Theorem Examples – An Ultimate Guide 2021

In this post we will learn about How to solve problems using master theorem examples.

  • Master Theorem is the method by which we can solve recursive function easily. It is the combination of mathematical and scientific approach. This theorem design in such a way by which we can solve all type of recursive function. Basically, Master Theorem consists of three cases which is use according to the problem.
  • In Master theorem one case use at a time among all three cases and it only depends upon the data given in the recursive problem.
  • When analyzing algorithms, we only care about the asymptotic behavior.

The Master Theorem

The master method depends on the following theorem.

T(n) = a T(n/b) + f (n) , 
where a ≥ 1, b > 1, and f is asymptotically positive.

What is Master Theorem?

Let a ≥ 1 and b > 1 be constants, let f(n) be a function, and let T(n) be defined on the non negative integers by the recurrence.
T(n)= aT(n/b)=f(n)
where we interpret n/b to mean either [n/b] or [n/b]. The T(n) can be bounded asymptotically as follows.
if f(n)= O(nlogb a-∈) for some constant ∈ > 0, then T(n) = Θ(nlogb a)
if f(n)= Θ(nlogb a) then T(n)=Θ(nlogb lgn)
if f(n)= Ω(nlogb a+∈) for some constant ∈ > 0 and if a f(n/b)≤cf(n) for some constant c < 1 and all sufficiently large n, then T(n)= Θ(f(n)).

Generic Form

The master theorem concerns recurrence relations of the form:

T(n) = a T(n/b) + f (n) , 
where a ≥ 1, b > 1, and f is asymptotically positive.
  • n is the size of the problem.
  • a is the number of sub problems in the recursion.
  • n/b is the size of each sub problem. (Assume that all sub problems are essentially the same size.)
  • f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the
  • problem and the cost of merging the solutions to the sub problems.

Case 1

Generic form

If f(n) = O (nc) where c < logb a (using Big O notation) then:
T (n) = Θ (nlogb a)

Case 2

Generic form

If it is true, for some constant k ≥ 0, that:
f(n) = Θ (nc logk n) where c = logb a
then:
T(n) = Θ (nc logk+1 n)

Case 3

Generic form

If it is true that:
f(n) = Ω (nc) where c > logb a
and if it is also true that:
af ( n/b ) ≤ kf(n) for some constant k < 1 and sufficiently large n (often called the regularity condition)
then:
T (n) = Θ (f(n))

Master Theorem Examples:

Let T (n) = T (n/2) + 1/2 n2 + n. What are the parameters?
Solution: a=1, b=2, d=2, Since 1 < 22, case 1 applies.
Thus we conclude that
 T (n) ∈ Θ(nd) = Θ(n2)
Let T (n) = 2T (n/4) + √n + 42. What are the parameters?
Solution: a = 2, b = 4, d = 1/2
Therefore which condition?
Since 2 = 41/2 , case 2 applies.
Thus we conclude that T (n) ∈ Θ(nd log n) = Θ(√n log n).
T(n) = 9T(n=3)+n. Here a = 9, b = 3, f(n) = n, and nlogb a = nlog3 9 = Θ(n2).
Since f(n) = O(nlog3 9−∈) for ∈ = 1, case 1 of the master theorem applies, and the solution is T(n) = Θ(n2).

When you cannot use master theorem?

You cannot use the master theorem if
T (n) is not monotone, ex: T (n) = sin n
f
(n) is not a polynomial, ex: T (n) = 2T (n2 ) + 2n
b
cannot be expressed as a constant, ex: T (n) = T (√n)

See also

introduction to Data structures and Algorithm tutorial.

How Many Types of Data Structures Are There? List of DS, Best Guide

Have you ever wondered How Many Types of Data Structures Are There? Here is complete List of Data structures and short note on each one of them.

How Many Types of Data Structures Are There?

Data Structures

This document gives extensive tutorials on all DS topics. A data file is a specific mechanism for organising an application data file. This page provides useful examples of different types of data. Array Linked Lists Stack Queues – Binary Trees – Search Trees. I can store the table that has the same types of files as our database in ArrayData Format. How can the linker of lists change in relation to them? The node exchanged is the same as any other database.

Data types and Data structures

Array

  • An array is a collection of items stored at contiguous memory locations.

Types of data:

There are 4 types of Data

  • Nominal,
  • Ordinal,
  • Discrete,
  • Continuous

Hash Table:

A Hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values.

Graphs.

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph

Tree

A Tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

Binary search tree

Binary Search Tree · The left subtree of a node contains only nodes with keys lesser than the node’s key.

Red-Black Tree

A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the color (red or black).

Data structure classification:

Data Structures are normally divided into two broad categories:
(1) Primitive Data Structures
(2) Non-Primitive Data Structures

Operations on data structure:

Operations on Data Structures are

  • Traversal,
  • Insertion,
  • Deletion,
  • Searching,
  • Sorting and
  • Merging.

B-tree

B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can have at most m-1 keys and m children.

Linear Probing

Linear probing is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key–value pairs and looking up the value associated with a given key

Need of Data Structures

The need of Data Structure includes efficiency and reusability. Data structure provides a way of organizing, managing, and storing data efficiently. With the help of data structure, the data items can be traversed easily.

Advantages of Data Structures

  • Data structure helps in efficient storage of data in the storage device.
  • Data structure usage provides convenience while retrieving the data from storage device.
  • Data structure provides effective and efficient processing of small as well as large amount of data.
  • Usage of proper data structure, can help programmer save lots of time or processing time while operations such as storage, retrieval or processing of data.
  • Manipulation of large amount of data can be carried out easily with the use of good data structure approach.
  • Most of the well organized data structures like Array, stack, queues, graph, tree, linked list has well built and pre-planned approach for operations like storage, addition, retrieval, manipulation, deletion, etc. While using them, programmer can be completely rely on these data structures.
  • Data structure usage can simply encourage reusability in long run as well.

Binary tree

A Binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Binary Heap

A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues.

Weight-balanced Tree

A weight-balanced tree is a binary search tree that stores the sizes of subtrees in the nodes.

Web References:

Best Data Structures and Algorithms Notes for Placement – 2021

Data Structures and Algorithms Notes for Placement

Data Structures and Algorithms Notes for Placement

Data Structures

Please check the tutorial section on the various data structures for more information. Data structures represent an efficient way of managing data in a computer system in order to enable efficient operations. The pages present instructions on data structures in detail.

There are questions related to:

Data Structures – Asymptotic Analysis

Asymptotic analysis is the process of calculating the running time of an algorithm in mathematical units to find the program’s limitations, or “run-time performance.” The goal is to determine the best case, worst case and average case time required to execute a given task. While not a method of deep learning training, Asymptotic analysis is a crucial diagnostic tool for programmers to evaluate an algorithm’s efficiency, rather than just its accuracy.

Data Structures – Algorithms Basics

Data Structures and Algorithms – Overview

Space Complexity

The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely.

Algorithm analysis

Analysis of algorithms is the determination of the amount of time and space resources required to execute it.

Need for Data Structure

The need of Data Structure includes efficiency and reusability. Data structure provides a way of organizing, managing, and storing data efficiently. With the help of data structure, the data items can be traversed easily.

Execution Time Cases

The time spent by the job actively using processor resources is its execution time. The execution time of each job instance from the same task is likely to differ. Execution times are of interest to real-time systems designers usually in the context of worst-case execution times.

Basic Terminology

Characteristics of an Algorithm

  • Unambiguous
  • Input
  • Output
  • Finiteness
  • Feasibility
  • Independent

Tell me the best way to write algorithms?

  • Obtaining a description of the problem.
  • Analyzing the problem.
  • Developing a high-level algorithm.
  • Refining the algorithm by adding more detail.
  • Reviewing the algorithm.

Algorithm Complexity

Algorithmic complexity is a measure of how long an algorithm would take to complete given an input of size n.

Time Complexity

Time required to analyze the given problem of particular size is known as the time complexity

Installation on UNIX/Linux

  1. sudo apt install GCC.
  2. GCC — version.
  3. cd Desktop.
  4. Key takeaway: Commands are case sensitive.
  5. touch program.c.
  6. GCC program.c -o program.
  7. Key takeaway: The executable file name can be different from the source file name.
  8. ./program.

Characteristics of a Data Structure

  • Linear
  • Non-Linear
  • Static
  • Homogenous
  • Non-Homogenous
  • Dynamic
  • Time Complexity
  • Space Complexity

Tell me the Abstract Data Type (ADT)?

Tell me the use of data structure?

  • Data Structures allow programmers to manage the data in the most efficient manner that enhances the algorithm’s performance.
  • They allow the implementation of a scientific approach as against traditional methodologies. When it comes to aspects such as processing speed, handling or multiple requests and searching through numerous records, data structures prove handy.
  • They allow efficient use of memory. Data structures optimize memory usage. This makes an impact usually in situations that involve the processing of huge datasets.
  • Data structures are reusable. They can be integrated as a package into a library. These libraries can be used in various situations by various stakeholders as needed.
  • They allow multiple solutions for a particular problem, allowing the user to select the data structure to solve the problem in the best way.

Local environment setup

Data Structures Books

Download Data Structures and Algorithms Notes for Placement

Web Reference:

Data Structures and Algorithms Quick Revision Best Guide

Here is a complete guide of Data Structures and Algorithms Quick Revision for students and Aspirants who wants to appear for coding interviews.

Data Structures and Algorithms Quick Revision

These pages give detailed tutorials describing various data structure types. Data structures provide an efficient way to store data on any computing system. You will find several articles about each information structure here.

Topics:

Data Structures – Asymptotic Analysis

Asymptotic analysis is the process of calculating the running time of an algorithm in mathematical units to find the program’s limitations, or “run-time performance.” The goal is to determine the best case, worst case and average case time required to execute a given task. While not a method of deep learning training, Asymptotic analysis is a crucial diagnostic tool for programmers to evaluate an algorithm’s efficiency, rather than just its accuracy.

Data Structures – Algorithms Basics

Space Complexity

The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely.

Algorithm analysis

Analysis of algorithms is the determination of the amount of time and space resources required to execute it.

Need for Data Structure

The need of Data Structure includes efficiency and reusability. Data structure provides a way of organizing, managing, and storing data efficiently. With the help of data structure, the data items can be traversed easily.

Execution Time Cases

The time spent by the job actively using processor resources is its execution time. The execution time of each job instance from the same task is likely to differ. Execution times are of interest to real-time systems designers usually in the context of worst-case execution times.

Characteristics of an Algorithm

  • Unambiguous
  • Input
  • Output
  • Finiteness
  • Feasibility
  • Independent

Tell me the best way to write algorithms?

  • Obtaining a description of the problem.
  • Analyzing the problem.
  • Developing a high-level algorithm.
  • Refining the algorithm by adding more detail.
  • Reviewing the algorithm.

Algorithm Complexity

  • Algorithmic complexity is a measure of how long an algorithm would take to complete given an input of size n.

Time Complexity

  • Time required to analyze the given problem of particular size is known as the time complexity

Characteristics of a Data Structure

  • Linear
  • Non-Linear
  • Static
  • Homogenous
  • Non-Homogenous
  • Dynamic
  • Time Complexity
  • Space Complexity

Local environment setup

Setting up local development environment.

Learn Latest Tutorials:

Download these concise Data Structures and Algorithms Quick Revision

Data Structures and Algorithms Refresher – Best Guide

Here is an Amazing guide on Data Structures and Algorithms Refresher for students and for job seekers who are looking for Refreshing their Data Structures and algorithms skill during interviews and exams.

Data Structures and Algorithms Refresher

Data Structures

Here is an overview tutorial that covers data structure techniques and themes. A data structure refers to a special process to organizing data into computers in order for them to efficiently be used. Offers information and guidance on a variety of database types.

Topics cover the following:

Specifically, we need to store lists with the same data types using array data structure. List length can be determined by interpolative or recursive code.

Data Structures Asymptotic Analysis

Asymptotic analysis is the process of calculating the running time of an algorithm in mathematical units to find the program’s limitations, or “run-time performance.” The goal is to determine the best case, worst case and average case time required to execute a given task. While not a method of deep learning training, Asymptotic analysis is a crucial diagnostic tool for programmers to evaluate an algorithm’s efficiency, rather than just its accuracy.

7 Best Data Structures and Algorithms Courses for Programmers

Data Structures – Algorithms Basics

These are the best courses to learn Data Structure and Algorithms for both Interviews and to become a better software Engineer

Space Complexity:

The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely.

Algorithm Analysis:

Analysis of algorithms is the determination of the amount of time and space resources required to execute it.

Need for Data Structure

The need of Data Structure includes efficiency and reusability. Data structure provides a way of organizing, managing, and storing data efficiently. With the help of data structure, the data items can be traversed easily.

Execution Time Cases

The time spent by the job actively using processor resources is its execution time. The execution time of each job instance from the same task is likely to differ. Execution times are of interest to real-time systems designers usually in the context of worst-case execution times.

Characteristics of an Algorithm

  • Unambiguous
  • Input
  • Output
  • Finiteness
  • Feasibility
  • Independent

Tell me the best way to write algorithms?

  1. Obtaining a description of the problem.
  2. Analyzing the problem.
  3. Developing a high-level algorithm.
  4. Refining the algorithm by adding more detail.
  5. Reviewing the algorithm.

Algorithm Complexity

Algorithmic complexity is a measure of how long an algorithm would take to complete given an input of size n.

Time Complexity

Time required to analyze the given problem of particular size is known as the time complexity

Characteristics of a Data Structure

  • Linear
  • Non-Linear
  • Static
  • Homogenous
  • Non-Homogenous
  • Dynamic
  • Time Complexity
  • Space Complexity

Local environment setup:

Setting up local development environment.

The C compiler

  • A compiler is a special program that processes statements written in a particular programming language and turns them into machine language or “code” that a computer’s processor uses

Text Editor

  • Text Editor is a free app that allows you to create, open, and edit text files on your computer and Google Drive.
Types of Data Structures

Data Structures and Algorithms in C++ Best Guide

Here is a complete guide on Data Structures and Algorithms in C++

Learn Data Structures and Algorithms in C++

Data Structures and Algorithms in C:

Data structure is an arrangement of data in a computer’s memory or disk. Data structures include Arrays, StacksQueues, linked lists, binary trees, and hash tables, and etc.

Data Structure = Organized Data + Allowed Operations.

An Algorithm is sequence of non ambiguous instructions for solving a problem in a finite amount of a time.

Types of Data Structures and Algorithms:

Types of Data Structure

Types of Data Structures

Types of Algorithms:

  • Simple recursive algorithms.
  • Backtracking algorithms.
  • Divide and conquer algorithms.
  • Dynamic programming algorithms.
  • Greedy algorithms.
  • Branch and bound algorithms.
  • Brute force algorithms.
  • Randomized algorithms

List of All C Programming, Data Structures and Algorithms

Data Types

Primitive Types

  • Boolean, true or false.
  • Character
  • Floating-point numbers, limited-precision approximations of real number values.
  • Including single-precision and double-precision IEEE 754 floats, among others
  • Fixed-point numbers
  • Integer, integral or fixed-precision values
  • Reference (also called a pointer or handle), a small value referring to another object’s address in memory, possibly a much larger one
  • Enumerated type, a small set of uniquely named values
  • Date Time, value referring to Date and Time

Composite types or non-primitive type

  • Array
  • Record also called structure
  • Union

Abstract Data types

  • Container
  • List
  • Tuple
  • Associative array, Map
  • Multimap
  • Set
  • Multiset (bag)
  • Stack
  • Queue (example Priority queue)
  • Double-ended queue
  • Graph (example Tree, Heap)

Linear Data Structures

  • Arrays
  • Array
  • Bit array
  • Bit field
  • Bitboard
  • Bitmap
  • Circular buffer
  • Control table
  • Image
  • Dope vector
  • Dynamic array
  • Gap buffer
  • Hashed array tree
  • Lookup table
  • Matrix
  • Parallel array
  • Sorted array
  • Sparse matrix
  • Iliffe vector
  • Variable-length array
  • Lists
  • Doubly linked list
  • Array list
  • Linked list
  • Association list
  • Self-organizing list
  • Skip list
  • Unrolled linked list
  • VList
  • Conc-tree list
  • Xor linked list
  • Zipper
  • Doubly connected edge list also known as half-edge
  • Difference list
  • Free list
  • Trees
  • Binary trees
  • AA tree
  • AVL tree
  • Binary search tree
  • Binary tree
  • Cartesian tree
  • Conc-tree list
  • Left-child right-sibling binary tree
  • Order statistic tree
  • Pagoda
  • Randomized binary search tree
  • Red–black tree
  • Rope
  • Scapegoat tree
  • Self-balancing binary search tree
  • Splay tree
  • T-tree
  • Tango tree
  • Threaded binary tree
  • Top tree
  • Treap
  • WAVL tree
  • Weight-balanced tree
  • B-trees
  • B-tree
  • B+ tree
  • B*-tree
  • B sharp tree
  • Dancing tree
  • 2–3 tree
  • 2–3–4 tree
  • Queap
  • Fusion tree
  • Bx-tree
  • AList
  • Heaps
  • Heap
  • Binary heap
  • B-heap
  • Weak heap
  • Binomial heap
  • Fibonacci heap
  • AF-heap
  • Leonardo heap
  • 2–3 heap
  • Soft heap
  • Pairing heap
  • Leftist heap
  • Treap
  • Beap
  • Skew heap
  • Ternary heap
  • D-ary heap
  • Brodal queue
  • Trees
  • In these data structures each tree node compares a bit slice of key values.

Tree

  • Radix tree
  • Suffix tree
  • Suffix array
  • Compressed suffix array
  • FM-index
  • Generalised suffix tree
  • B-tree
  • Judy array
  • X-fast trie
  • Y-fast trie
  • Merkle tree
  • C tree
  • Multi-way trees
  • Ternary tree
  • K-ary tree
  • And–or tree
  • (a,b)-tree
  • Link/cut tree
  • SPQR-tree
  • Spaghetti stack
  • Disjoint-set data structure (Union-find data structure)
  • Fusion tree
  • Enfilade
  • Exponential tree
  • Fenwick tree
  • Van Emde Boas tree
  • Rose tree
  • Space-partitioning trees
  • These are data structures used for space partitioning or binary space partitioning.

Space-partitioning trees

  • Segment tree
  • Interval tree
  • Range tree
  • Bin
  • K-d tree
  • Implicit k-d tree
  • Min/max k-d tree
  • Relaxed k-d tree
  • Adaptive k-d tree
  • Quadtree
  • Octree
  • Linear octree
  • Z-order
  • UB-tree
  • R-tree
  • R+ tree
  • R* tree
  • Hilbert R-tree
  • X-tree
  • Metric tree
  • Cover tree
  • M-tree
  • VP-tree
  • BK-tree
  • Bounding interval hierarchy
  • Bounding volume hierarchy
  • BSP tree
  • Rapidly exploring random tree

Application-specific Trees:

  • Abstract syntax tree
  • Parse tree
  • Decision tree
  • Alternating decision tree
  • Minimax tree
  • Expectiminimax tree
  • Finger tree
  • Expression tree
  • Log-structured merge-tree
  • Lexicographic Search Tree

Hash-based Structures:

  • Bloom filter
  • Count–min sketch
  • Distributed hash table
  • Double hashing
  • Dynamic perfect hash table
  • Hash array mapped trie
  • Hash list
  • Hash table
  • Hash tree
  • Hash trie
  • Koorde
  • Prefix hash tree
  • Rolling hash
  • MinHash
  • Quotient filter
  • Ctrie

Graphs

  • Adjacency list
  • Adjacency matrix
  • Graph-structured stack
  • Scene graph
  • Decision tree
  • Binary decision diagram
  • Zero-suppressed decision diagram
  • And-inverter graph
  • Directed graph
  • Directed acyclic graph
  • Propositional directed acyclic graph
  • Multigraph
  • Hypergraph

List of All Algorithms:

Graph algorithms

  • Coloring algorithm: Graph coloring algorithm.
  • Hopcroft–Karp algorithm: convert a bipartite graph to a maximum cardinality matching
  • Hungarian algorithm: algorithm for finding a perfect matching
  • Prüfer coding: conversion between a labeled tree and its Prüfer sequence
  • Tarjan’s off-line lowest common ancestors algorithm: computes lowest common ancestors for pairs of nodes in a tree
  • Topological sort: finds linear order of nodes (e.g. jobs) based on their dependencies.
  • Minimum spanning tree
  • Borůvka’s algorithm
  • Kruskal’s algorithm
  • Prim’s algorithm
  • Reverse-delete algorithm
  • Shortest path problem
  • Bellman–Ford algorithm: computes shortest paths in a weighted graph (where some of the edge weights may be negative)
  • Dijkstra’s algorithm: computes shortest paths in a graph with non-negative edge weights
  • Floyd–Warshall algorithm: solves the all pairs shortest path problem in a weighted, directed graph
  • Johnson’s algorithm: All pairs shortest path algorithm in sparse weighted directed graph
  • Transitive closure problem: find the transitive closure of a given binary relation
  • Traveling salesman problem
  • Christofides algorithm
  • Nearest neighbour algorithm

Graph search

  • A: special case of best-first search that uses heuristics to improve speed B: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals)
  • Backtracking: abandons partial solutions when they are found not to satisfy a complete solution
  • Beam search: is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement
  • Beam stack search: integrates backtracking with beam search
  • Best-first search: traverses a graph in the order of likely importance using a priority queue
  • Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph
  • Breadth-first search: traverses a graph level by level
  • Brute-force search: An exhaustive and reliable search method, but computationally inefficient in many applications.
  • D: an incremental heuristic search algorithm Depth-first search: traverses a graph branch by branch Dijkstra’s algorithm: A special case of A for which no heuristic function is used
  • General Problem Solver: a seminal theorem-proving algorithm intended to work as a universal problem solver machine.
  • Iterative deepening depth-first search (IDDFS): a state space search strategy
  • Jump point search: An optimization to A* which may reduce computation time by an order of magnitude using further heuristics.
  • Lexicographic breadth-first search (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph
  • Uniform-cost search: a tree search that finds the lowest-cost route where costs vary

Selection Algorithms

  • Quickselect
  • Introselect

Sequence search

  • Linear search: locates an item in an unsorted sequence
  • Selection algorithm: finds the kth largest item in a sequence
  • Ternary search: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa
  • Sorted lists
  • Binary search algorithm: locates an item in a sorted sequence
  • Fibonacci search technique: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers
  • Jump search (or block search): linear search on a smaller subset of the sequence
  • Predictive search: binary-like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search.
  • Uniform binary search: an optimization of the classic binary search algorithm

Sequence Merging:

  • Simple merge algorithm
  • k-way merge algorithm
  • Union (merge, with elements on the output not repeated)

Sequence Sorting:

  • Bubble sort: for each pair of indices, swap the items if out of order
  • Comb sort
  • Gnome sort
  • Odd–even sort
  • Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice

Also Read these Tutorials:

Learn Data structures in Java

Computer Science Algorithms and Data structures

data structures basics for beginners

learn Data structures in c

DSA using c++

Web References:

Big omega Functions and Examples

Big omega Functions and Examples – Complete Guide

Sometimes, we want to say that an algorithm takes at least a certain amount of time, without providing an upper bound. We use big-Ω notation; that’s the Greek letter “omega.”

Big Omega definition

A function t(n) is said to be in Ω(g(n)), denoted t(n) ∈ Ω(g(n)), if t(n) is bounded both above and below by some positive constant multiples of g(n) for all large n, i.e., if there exist some positive constants c1 and c2 and some
nonnegative integer n0 such that c2g(n) ≤ t(n) ≤ c1g(n) for all n ≥ n0

  • Big Omega(Ω) function is used in computer science to describe the performance or complexity of an algorithm. If a running time is Ω(f(n)), then for large enough n, the running time is at least k⋅f(n) for some constant k.
  • Big Omega describes the lower bound of an algorithm.
  • Big-Omega is commonly denoted by Ω, is an Asymptotic Notation to denote the best case analysis of an algorithm.
  • Ω notation provides an asymptotic lower bound.
  • Sometimes, we want to say that an algorithm takes at least a certain amount of time, without providing an upper bound.
  • We use big-Ω notation to show that least certain amount of time for an algorithm.
  • If running time is Ω(f(n)), then for large enough n, the running time is at least k. f(n) for some constant k.

Note:

  • Best case Ω Of an algorithm describes a lower bound for all combinations of input. It implies that the function can never get any better than the specified value. For example, when sorting an array, the best case is when the array is already correctly sorted.
  • Worst case Ω describes a lower bound for worst-case input combinations. It is possibly greater than the best case. For example, when sorting an array, the worst case is when the array is sorted in reverse order.
Big omega Functions and Examples
Figure: Big Omega

Big Omega Examples:

  • n3 + 4n2 = Ω(n2)

Proof:
Here, we have f(n) = n3 + 4n2, and g(n) = n2
It is not too hard to see that if n ≥ 0,
n3 ≤ n3 + 4n2
• We have already seen that if n ≥ 1,
n2 ≤ n3
• Thus when n ≥ 1,
n2 ≤ n3 ≤ n3 + 4n2
• Therefore,
1n2 ≤ n3 + 4n2 for all n ≥ 1
• Thus, we have shown that n3 + 4n2 = Ω(n2)
(by definition of Big-Ω, with n0 = 1, and c = 1.)

  • Let f(n) = 5.5n2 – 7n.

We need to verify whether f(n) is Ω(n2).
Let c be a constant such that 5.5n2 – 7n ≥ cn2, or, n ≥ 7/5.5-c.
Fix c = 3, to get n ≥ 2.8. So, our n0 = 2.8 and c = 3. This shows that there exists positive constants c = 3 and n0 = 2.8 such that 0 ≤ cn2 ≤ f(n), ∀n ≥ n0.

Big omega function:

Similar to big O notation, big Omega(Ω) function is used in computer science to describe the performance or complexity of an algorithm.

Binary and Binary Search Tree – Best Guide

Trees are used to impose a hierarchical structure on a collection of data items.

Here is complete Guide on Binary and Binary Search Trees.

What is Tree?

A tree is a set of one or more nodes T such that: there is a specially designated node called a root The remaining nodes are partitioned into n disjointed set of nodes 1, T2,…,Tn, each of which is a tree.

Figure: A Tree Structure
  • This is a tree because it is a set of nodes {A,B,C,D,E,F,G,H,I}, with node A as a root node and the remaining nodes partitioned into three disjointed sets {B,G,H,I}, { C,E,F} and {D}, respectively.
  • Each of these sets is a tree because each satisfies the aforementioned definition properly.
Figure: A Non Tree Structure
  • Even though this is a set of nodes {A,B,C,D,E,F,G,H,I}, with node A as a root node, this is not a tree because the fact that node E is shared makes it impossible to partition nodes B through I into disjointed sets.

Degree of a Node of a Tree

  • The degree of a node of a tree is the number of subtrees having this node as a root. In other words, the degree is the number of descendants of a node. If the degree is zero, it is called a terminal or leaf node of a tree.

Degree of a Tree

  • The degree of a tree is defined as the maximum of degree of the nodes of the tree, that is, degree of tree = max (degree(node i) for I = 1 to n)

Level of a Node

  • We define the level of the node by taking the level of the root node as 1, and incrementing it by 1 as we move from the root towards the subtrees. So the level of all the descendants of the root nodes will be 2. The level of their descendants will be 3, and so on. We then define the depth of the tree to be the maximum value of the level of the node of the tree.

Binary Tree

  • A binary tree is a finite set of nodes that is either empty or it consists of a root and two disjoint binary trees called the left sub tree and the right sub tree.
  • A binary tree is a rooted tree in which every node has at most two children. A full binary tree is a tree in which every node has zero or two children. Also known as a proper binary tree. A perfect binary tree is a full binary tree in which all leaves (vertices with zero children) are at the same depth (distance from the root, also called height).
  • A binary tree is similar to a tree, but not quite the same. For a binary tree, each node can have zero, one, or two children. In addition, each child node is clearly identified as either the left child or the right child.

Binary Search Tree

  • A binary search tree is a binary tree in which the data in the nodes are ordered in a particular way. To be precise, starting at any given node, the data in any nodes of its left sub tree must all be less than the item in the given node, and the data in any nodes of its right sub tree must be greater than or equal to the data in the given node. For numbers this can obviously be done. For strings, alphabetical ordering is often used. For records of data, a comparison based on a particular field (the key field) is often used.

Binary Search Tree Example

Binary Search Tree Example
Figure: Binary Search Tree Example

Binary Search Tree In Data Structure

  • A binary tree is a type of data structure for storing data such as numbers in an organized way.
  • Binary search trees allow binary search for fast lookup, addition and removal of data items, and can be used to implement dynamic sets and lookup tables.
  • The order of nodes in a BST means that each comparison skips about half of the remaining tree, so the whole lookup takes time proportional to the binary logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables. Several variants of the binary search tree have been studied.

Binary Search Tree Algorithm

If root == NULL 
    return NULL;
If number == root->data 
    return root->data;
If number < root->data 
    return search(root->left)
If number > root->data 
    return search(root->right)

Binary Search Tree Search Algorithm

Step 1: IF ROOT -> DATA = ITEM OR ROOT = NULL
    Return ROOT
   ELSE
   IF ROOT < ROOT -> DATA
   Return search(ROOT -> LEFT, ITEM)
  ELSE
   Return search(ROOT -> RIGHT,ITEM)
  [END OF IF]
  [END OF IF]
Step 2: END

Reference:

Queue Data Structure

Queue Data Structure – Best Guide 2021

In everyday life, we encounter queues everywhere – a line of people waiting to buy a ticket or waiting to be served in a bank, all such lines of people are queues. The first person in line is the next one served, and when another person arrives, he/she joins the queue at the rear.

  • A Queue is a chronologically ordered list.
  • The difference between a stack and a queue is that, in a stack, elements are added and removed at the same end (the top), whereas in a queue, values are added at one end (the rear) and removed from the other end (the front).

Queue Definition

A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue).

  • The Queue ADT stores arbitrary objects
  • Insertions and deletions follow the first-in first-out (FIFO) scheme
  • Insertions are at the rear of the queue and removals are at the front of the queue.
Queue Data Structure
Source: Wikipedia

Main Queue operations

  • enqueue(object o): inserts element o at the end of the queue
  • dequeue(): removes and returns the element at the front of the queue.

Auxiliary Queue operations:

  • front(): returns the element at the front without removing it
  • size(): returns the number of elements stored
  • isEmpty(): returns a Boolean value indicating whether no elements are stored.

Exceptions:

  • Attempting the execution of dequeue or front on an empty queue throws an EmptyQueueException.

Operations of Queue

The following operations can be applied to a queue

  • InitQueue(Queue): creates an empty queue.
  • append(Item): inserts an item to the rear of the queue.
  • remove(Queue): removes an item from the front of the queue. Elements can only be added to the rear of the queue and removed from the front of the queue.
  • isEmpty(Queue): returns true if the queue is empty.

Array Implementation

  • data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority Queues are a subclass of Linear Lists, which maintain the First-In-First-Out order of elements. Insertion of elements is carried out at the ‘Tail‘ of the queue and deletion is carried out at the ‘Head‘ of the queue.
  • A queue is an ordered by position, not by value collection of data, with the following operations defined on it:

Operations

  • An array-based queue requires us to know two values a priori: the type of data contained in the queue, and the size of the array.
  • The queue itself is a structure containing three elements: Data, the array of data, Head, an index that keeps track of the first element in the queue (location where data is removed from the queue), and Tail, an index that keeps track of the last element in the queue (location where elements are inserted into the queue).

The operations that can be performed in a Queue are:
Initialize: Initialize internal structure; create an empty queue.

Pseudo-Code:
Set Head to 1
Set Tail to 1
Return the Queue to the user.

Enqueue: Add new element to the tail of the queue. This operation adds a new element at
the rear end of the queue.


Pseudo-Code:
If Queue is Full (Tail = Size of Queue + 1) Then
Output ―Overflow, Queue is full, cannot Enqueue.‖
Else
Place Element in Queue (Tail)
Increment Tail (Tail = Tail + 1)
Return the queue to the user.

Dequeue : Remove an element from the head of the queue. This operation removes an element only from the front of the queue.

Pseudo-Code:
If Queue is Empty (Head = Tail) Then
Output ―Underflow, Queue is empty, cannot dequeue.‖
Else
Element: = Queue(Head);
Move all the elements from head+1 to Size of Queue one step to the left
Return Element

Applications of Queues:

  • CPU Scheduler
  • Round-Robin Scheduling
  • Serving Requests
  • Buffers
  • Simulation of an Airport

Reference:

Stack Data Structure

Stack Data Structure – Best Guide 2021

A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack.

The basic implementation of a stack is also called a LIFO (Last In First Out).

Stack Data Structure Definition:

A stack data structure is a list of elements in which an element may be inserted or deleted only at one end, called me top of the stack. This means, in particular, that elements are removed from a stack in the reverse order of that in which they were inserted into the stack.

Special terminology is used for two basic operations associated with stacks:

(a) “Push” is the term used to insert an element into a stack.

(b) “Pop” is the term used to delete an element from a stack.

  • There are basically three operations that can be performed on stacks.
    1) Inserting an item into a stack (push).
    2) Deleting an item from the stack (pop).
    3) Displaying the contents of the stack(pip).
Stack Data Structure
Fig: Wikipedia

Below are some of operations a stack data type supports:

Stack<item-type> Operations
push (new-item :item-type)
Adds an item onto the stack.
top ():item-type
Returns the last item pushed onto the stack.
pop ()
Removes the most-recently-pushed item from the stack.
is-empty ():Boolean
True if no more items can be popped and there is no top item.
is-full ():Boolean
True if no more items can be pushed.
get-size ():Integer
Returns the number of elements on the stack.
  • All operations except get-size() can be performed in O(1) time. get-size() runs in at worst O(N).

Array Implementation of a Stack Data Structure:

When an array is used to implement a stack, the push and pop operations are realized by using the operations available on an array. The limitation of an array implementation is that the stack cannot grow and shrink dynamically as per the requirement.

C program to implement a stack using an array.

#include <stdio.h>
#define MAX 10 /* The maximum size of the stack */
#include <stdlib.h>

void push(int stack[], int *top, int value)
{
   if(*top < MAX )
   {
      *top = *top + 1;
      stack[*top] = value;
   }
  else
  {
      printf("The stack is full can not push a value\n");
      exit(0);
   }
}

void pop(int stack[], int *top, int * value)
{
   if(*top >= 0 )
   {
       *value = stack[*top];
      *top = *top - 1;
   }
   else
   {
      printf("The stack is empty can not pop a value\n");
      exit(0);
   }
}

void main()
{
   int stack[MAX];
   int top = -1;
   int n,value;
   do
   {
      do
      {
            printf("Enter the element to be pushed\n");
         scanf("%d",&value);
         push(stack,&top,value);
            printf("Enter 1 to continue\n");
         scanf("%d",&n);
      } while(n == 1);

      printf("Enter 1 to pop an element\n");
      scanf("%d",&n);
      while( n == 1)
      {
            pop(stack,&top,&value);
         printf("The value poped is %d\n",value);
            printf("Enter 1 to pop an element\n");
            scanf("%d",&n);
      }
      printf("Enter 1 to continue\n");
      scanf("%d",&n);
   } while(n == 1);
}

Example Output:

Enter the element to be pushed

10

Enter 1 to continue

1

Enter the element to be pushed

20

Enter 1 to continue

0

Enter 1 to pop an element

1

The value popped is 20
Enter 1 to pop an element

0

Enter 1 to continue

1

Enter the element to be pushed

40

Enter 1 to continue

1

Enter the element to be pushed

50

Enter 1 to continue

0

Enter 1 to pop an element

1

The value popped is 50

Enter 1 to pop an element

1

The value popped is 40 Enter 1 to pop an element

1

The value popped is 10 Enter 1 to pop an element

0

Enter 1 to continue

0

Linked List Implementation

type Stack<item_type>
data list:Singly Linked List<item_type>
constructor()
list := new Singly-Linked-List()
end constructor

When you want to push something onto the list, you simply add it to the front of the linked list. The previous top is then ”next” from the item being added and the list’s front pointer points to the new item.

method push(new_item:item_type)
list.prepend(new_item)
end method

To look at the top item, you just examine the first item in the linked list

method top():item_type
return list.get-begin().get-value()
end method

When you want to pop something off the list, simply remove the first item from the linked list.

method pop()
list.remove-first()
end method

A check for emptiness is easy. Just check if the list is empty

method is-empty():Boolean
return list.is-empty()
end method

A check for full is simple. Linked lists are considered to be limitless in size.

method is-full():Boolean
return False
end method

A check for the size is again passed through to the list.

method get-size():Integer
return list.get-size()
end method
end type
  • In a linked list, accessing the first element is an O(1) operation because the list contains a pointer that checks for empty as done here are also O(1). Most of the time, users of a Stack do not use the getSize() operation, and so a bit of space can be saved by not optimizing it.

Complexity:

All operations are O(1) with exception of occasional push and clear, which should replace all entries by null in order to let them be garbage-collected. Array implementation does not replace null entries. The Vector implementation does.

Program for implementation of a stack using the linked list.

# include <stdio.h>
# include <stdlib.h>
struct node
{
   int data;
   struct node *link;
};
struct node *push(struct node *p, int value)
{
   struct node *temp;
   temp=(struct node *)malloc(sizeof(struct node));
       /* creates new node
       using data value
       passed as parameter */
   if(temp==NULL)
   {
      printf("No Memory available Error\n");
      exit(0);
   }
   temp->data = value;
   temp->link = p;
   p = temp;
   return(p);
}

struct node *pop(struct node *p, int *value)
{
   struct node *temp;
   if(p==NULL)
   {
      printf(" The stack is empty can not pop Error\n");
      exit(0);
   }
   *value = p->data;
   temp = p;
   p = p->link;
   free(temp);
   return(p);
}

void main()
{
   struct node *top = NULL;
   int n,value;
   do
   {
      do
      {
            printf("Enter the element to be pushed\n");
         scanf("%d",&value);
         top = push(top,value);
         printf("Enter 1 to continue\n");
         scanf("%d",&n);
      } while(n == 1);

      printf("Enter 1 to pop an element\n");
      scanf("%d",&n);
      while( n == 1)
      {
            top = pop(top,&value);
         printf("The value poped is %d\n",value);
            printf("Enter 1 to pop an element\n");
            scanf("%d",&n);
      }
      printf("Enter 1 to continue\n");
      scanf("%d",&n);
   } while(n == 1);
}

Example Output:

Input and Output
Enter the element to be pushed

10

Enter 1 to continue

1

Enter the element to be pushed

20

Enter 1 to continue

0

Enter 1 to pop an element

1

The value popped is 20
Enter 1 to pop an element

1

The value poped is 10
Enter 1 to pop an element

0

Enter 1 to continue

1

Enter the element to be pushed

30

Enter 1 to continue

1

Enter the element to be pushed

40

Enter 1 to continue

0

Enter 1 to pop an element

1

The value popped is 40
Enter 1 to pop an element

0

Enter 1 to continue

1

Enter the element to be pushed

50

Enter 1 to continue

0

Enter 1 to pop an element

1

The value popped is 50
Enter 1 to pop an element

1

The value popped is 30
Enter 1 to pop an element

0

Enter 1 to continue

0

Applications of Stack Data Structure