“Whenever we want to perform analysis of an algorithm, we need to calculate the complexity of that algorithm. But when we calculate the complexity of an algorithm it does not provide the exact amount of resource required.”

• Asymptotic Notations are mathematical tools that allow you to analyze an algorithm’s running time by identifying its behavior as its input size grows.
• Asymptotic notation of an algorithm is a mathematical representation of its complexity.

There are three cases to calculate the time complexity :

• Best Case − Minimum time required for program execution.
• Average Case − Average time required for program execution.
• Worst Case − Maximum time required for program execution.

Majorly, we use THREE types of Asymptotic Notations and those are as follows…

1. Big – Oh (O)
2. Big – Omega (Ω)
3. Big – Theta (Θ

Big – Oh Notation (O)

Big – Oh notation is used to define the upper bound of an algorithm in terms of Time Complexity. That means Big – Oh notation always indicates the maximum time required by an algorithm for all input values. That means Big – Oh notation describes the worst case of an algorithm time complexity.

Big – Oh Notation can be defined as follows…

Consider function f(n) as time complexity of an algorithm and g(n) is the most significant term. If f(n) <= C g(n) for all n >= n0, C > 0 and n0 >= 1. Then we can represent f(n) as O(g(n)).

f(n) = O(g(n))

Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on X-Axis and time required is on Y-Axis

In above graph after a particular input value n0, always C g(n) is greater than f(n) which indicates the algorithm’s upper bound.

Big – Omega Notation (Ω)

Big – Omega notation is used to define the lower bound of an algorithm in terms of Time Complexity. That means Big-Omega notation always indicates the minimum time required by an algorithm for all input values. That means Big-Omega notation describes the best case of an algorithm time complexity.

Big – Omega Notation can be defined as follows…

Consider function f(n) as time complexity of an algorithm and g(n) is the most significant term. If f(n) >= C g(n) for all n >= n0, C > 0 and n0 >= 1. Then we can represent f(n) as Ω(g(n)).

f(n) = Ω(g(n))

Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on X-Axis and time required is on Y-Axis

In above graph after a particular input value n0, always C g(n) is less than f(n) which indicates the algorithm’s lower bound.

Big – Theta Notation (Θ)

Big – Theta notation is used to define the average bound of an algorithm in terms of Time Complexity. That means Big – Theta notation always indicates the average time required by an algorithm for all input values. That means Big – Theta notation describes the average case of an algorithm time complexity.

Big – Theta Notation can be defined as follows…

Consider function f(n) as time complexity of an algorithm and g(n) is the most significant term. If C1 g(n) <= f(n) <= C2 g(n) for all n >= n0, C1 > 0, C2 > 0 and n0 >= 1. Then we can represent f(n) as Θ(g(n)).

f(n) = Θ(g(n))

Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on X-Axis and time required is on Y-Axis

In above graph after a particular input value n0, always C1 g(n) is less than f(n) and C2 g(n) is greater than f(n) which indicates the algorithm’s average bound.

Time Complexity is a concept in computer science that deals with the quantification of the amount of time taken by a set of code or algorithm to process or run as a function of the amount of input.

The efficiency of an algorithm depends on two parameters:

• Time Complexity
• Space Complexity

What is Time complexity?

The time complexity of an algorithm is the total amount of time required by an algorithm to complete its execution. Generally, the running time of an algorithm depends upon the following…

1. Whether it is running on Single processor machine or Multi processor machine.
2. Whether it is a 32 bit machine or 64 bit machine.
3. Read and Write speed of the machine.
4. The amount of time required by an algorithm to
5. perform Arithmetic operations, logical operations, return value and assignment operations etc.,
6. Input data

What is Space complexity?

Total amount of computer memory required by an algorithm to complete its execution is called as space complexity of that algorithm. Generally, when a program is under execution it uses the computer memory for THREE reasons. They are as follows..

1. Instruction Space: It is the amount of memory used to store compiled version of instructions.
2. Environmental Stack: It is the amount of memory used to store information of partially executed functions at the time of function call.
3. Data Space: It is the amount of memory used to store all the variables and constants.

ADT is a collection of data together with a set of operations on data.

ADT = Data + Operations

Definition : Abstract Data Type (ADT) is defined as a mathematical model with a collection of operations defined on that model.

• The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented.
• It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations.
• It is called “abstract” because it gives an implementation-independent view. 

The process of providing only the essentials and hiding the details is known as abstraction. 

The above figure shows the ADT model. There are two types of models in the ADT model, i.e., the public function and the private function. The ADT model also contains the data structures that we are using in a program.

TYPES: There are several types

1. List ADT

View of list

• The data is generally stored in key sequence in a list which has a head structure consisting of count, pointers and address of compare function needed to compare the data in the list.
• The data node contains the pointer to a data structure and a self-referential pointer which points to the next node in the list.

The List ADT Functions is given below:

• get() – Return an element from the list at any given position.
• insert() – Insert an element at any position of the list.
• remove() – Remove the first occurrence of any element from a non-empty list.
• removeAt() – Remove the element at a specified location from a non-empty list.
• replace() – Replace an element at any position by another element.
• size() – Return the number of elements in the list.
• isEmpty() – Return true if the list is empty, otherwise return false.
• isFull() – Return true if the list is full, otherwise return false.

2. Stack ADT

View of stack

• In Stack ADT Implementation instead of data being stored in each node, the pointer to data is stored.
• The program allocates memory for the data and address is passed to the stack ADT.
  • push() – Insert an element at one end of the stack called top.
  • pop() – Remove and return the element at the top of the stack, if it is not empty.
  • peek() – Return the element at the top of the stack without removing it, if the stack is not empty.
  • size() – Return the number of elements in the stack.
  • isEmpty() – Return true if the stack is empty, otherwise return false.
  • isFull() – Return true if the stack is full, otherwise return false.

3. Queue ADT

View of Queue

• The queue abstract data type (ADT) follows the basic design of the stack abstract data type.
• Each node contains a void pointer to the data and the link pointer to the next element in the queue. The program’s responsibility is to allocate memory for storing the data.
  • enqueue() – Insert an element at the end of the queue.
  • dequeue() – Remove and return the first element of the queue, if the queue is not empty.
  • peek() – Return the element of the queue without removing it, if the queue is not empty.
  • size() – Return the number of elements in the queue.
  • isEmpty() – Return true if the queue is empty, otherwise return false.
  • isFull() – Return true if the queue is full, otherwise return false.

Features of ADT:

1. Abstraction
2. Better Conceptualization
3. Encapsulation
4. Data Abstraction
5. Data Structure Independence

Advantages & Disadvantages :

Advantages:	Disadvantages:
Encapsulation	Overhead
Abstraction	Complexity
Data Structure Independence	Learning
Modularity	Cost

Classifications of data structures :

Data structures are often classified by their characteristics. The following three characteristics are examples:

1. Linear or non-linear : This characteristic describes whether the data items are arranged in sequential order, such as with an array, or in an unordered sequence, such as with a graph.

2. Homogeneous or heterogeneous : This characteristic describes whether all data items in a given repository are of the same type. One example is a collection of elements in an array, or of various types, such as an abstract data type defined as a structure in C or a class specification in Java.

3. Static or dynamic : This characteristic describes how the data structures are compiled. Static data structures have fixed sizes, structures and memory locations at compile time. Dynamic data structures have sizes, structures and memory locations that can shrink or expand, depending on the use.

What are the characteristics of data structures :

Data structures are systematized ways of organizing data in order to use that data efficiently. There are some characteristics of every data structure that make it efficient.

Characteristics of a data structure : There are three main characteristics:

• Correctness
• Time complexity
• Space complexity

1. Correctness : Data Structure implementation should implement its interface correctly. There are further two types of correctness:

• Partial correctness : An algorithm is partially correct if it receives valid input and gets terminated. We can prove it through empirical analysis or by testing it on a few cases.
• Total correctness : An algorithm is totally correct if it receives valid inputs and gets terminated, and always returns the correct output. We can prove this formal reasoning or mathematically, for instance, by proof by induction.

2. Time Complexity : The running time or execution time of a data structure as a function of the length of the input is known as time complexity.

Example: The access time complexity of an array is O(1). This is because you can directly access any element of the array using its index.

3. Space Complexity : When an algorithm or data structure runs on your computer, it needs some sort of space/memory. The total memory space your data structure needs for its execution or to work properly is known as space complexity.

Example: A hash table has a space complexity of O(n).