## Write short note on ADT.

**What is ADT?**- ADT stands for Abstract Data Type.
- It is a mathematical model of a data structure.
- ADT describes a container which holds a finite number of objects where the objects may be associated through a given binary relationship.
- It is a logical description of how we view the data and the operations that are allowed without regard to how they will be implemented.
- It concerns only with what the data is representing and not with how it will eventually be constructed.
- It is a set of objects and operations, for example: list, insert, delete, serach, sort.

**Abstract Data Types (ADTs)**
**Following are the some basic ADTs of data structure:**
Stack

Queue

Linked List

**1. Stack**- It is a list where insert and remove take place only at the top.
- It performs LIFO(Last In First Out) operation.

**Operations of Stack**
**Push:** Insert element on top of stack.

**Pop:** Remove element from top of stack.

**Top:** Return element at top of stack.

**2. Queue**- It is a list where insert takes place at the back, but remove takes place at the front.
- It performs FIFO(First In First Out) operation.

**Operations of Queue**
**Enqueue:** Insert element at the back of the queue.

**Dequeue:** Remove and return element from the front of the queue.

**3. Linked List**- It is a linear collection of data elements, called nodes pointing to the next node by means of pointer.
- Each node consists of its own data and the address of the next node and forms and chain.
- It is used to create trees and graphs.

**Advantages of ADT**- It is reusable and ensures robust data structure.
- It can be re-used at several places.
- It reduces coding efforts.
- Encapsulation ensures that data cannot be corrupted.
- It is based on principles of Object Oriented Programming (OOP) and Software Engineering (SE).

## Explain space and time complexity.

**Time Complexity:** It is the amount of time an algorithm takes in terms of the amount of input data to algorithm. It is calculated on the basis of different criteria such as:

- The number of times the memory is being accessed.
- The number of comparisons between variables.
- The number of time loops is executed etc.

**Space Complexity:** It is the amount of memory an algorithm takes in terms of the amount of input data to the program. If an algorithm takes less time to execute and takes less memory, then it is considered as best algorithm.

**Example:**
The running time of a loop is, at most, the running time of the statements inside the loopmultiplied by the number of iterations.

for (i=1; i<=n; i++)

{

m = m + 2; //constant time, c

}

Total time = a constant c * n = cn = 0(n)

## Find the time complexity of given below code. Ignore syntax error.

Fun()

{

Inti = 1, s = 1;

while(s<=n)

{

i++;

s = s + i;

printf(“CareerRide”);

}

}

**Solution:**
Let us see how the value of s is change with respect to i. The loop will stop when the condition s<=n.

Suppose that it will stop after k iteration. Means the condition s<=n met after k iteration. The value of s is summation of i.

k(k+1)/2 > n

k2 + k > 2n

k = O (n1/2)

**Output**
Time complexity = O (n^{1/2})## Find the time complexity of given below code. Ignore syntax error.

Fun()

{

int i, j, k, n;

for (i=1; i<=n; i++)

{

for (j=1; j<=i; j++)

{

for (k=1; k<=100; k++)

{

Printf(“CareerRide”);

}

}

}

}

**Solution:**
If i = | 1 | 2 | 3 | 4 | 5 | | n |

Then inner loop will execute j<=i | 1 time | 2 time | 3 time | 4 time | 5 time | .... and so on | n time |

Most inner loop will execute K<=100 | 100 times | 200 times | 300 times | 400 times | 500 times | | n * 100 times |

**So the total time will be**
= 100 + 2 * 100 + 3 * 100 + 4 * 100....n * 100

= 100 (1 + 2 + 3 + 4………n)

= 100 [n(n + 1)/2]

= 100 [(n

^{2} + n)/2]

= O (n

^{2})

**Output**
Time complexity = O (n^{2})## Find the time complexity of given below code. Ignore syntax error.

A()

{

for(i = 1; i<n; i = i * 2)

{

Printf(“careerRide”);

}

}

**Solution:**
Initial value of i is 1 and it is incremented by the expression i = i * 2.

I = | 1 | 2 | 4 | 8 | 16 | 32 |

i = i * 2 | 2 | 4 | 8 | 16 | 32 | 64 |

**So the series will be as follows.**
2

^{0}, 2

^{1}, 2

^{2}, 2

^{3}, 2

^{4}, 2

^{5}, .......,

**Let us assume after k iteration loop will stop, so**
2^{k} = n

K = log_{2}n

**Output**
Time complexity = O (Log_{2}n)## Find the time complexity of given below code. Ignore syntax error.

A()

{

for(i=n/2; i<=n; i++)

{

for(j=1; j<=n/2; j++)

{

for(k=1; k*lt;=n; k=k*2)

{

Printf(“CareerRide”);

}

}

}

}

**Solution:**
The first loop will execute n/2 times, second loop will also execute n/2 times. According to above question the time complexity of last loop will be log

_{2}n.

So the time complexity will be = n/2 * n2 * log

_{2}n.

= n

^{2}log

_{2}n.

**Output**
Time complexity = O (n^{2}log_{2}n)