# DSA Part 1: Introduction

## Asymptotic Notations

Time taken by a program is always +ve. Input provided is also always +ve.

Hence, analysis of an algorrithm is done always in the first quadrant.

### Big-O Notation

### Big-Ω Notation

### Big-Θ Notation

## Complexity analysis of a problem

### Steps to approach a problem

- Read lengthy and unusual paragraphs to decode the problem statement.
- Observe the input format.
- Observe the output format.
- Analyze the given contraints
- Time Limit : 0.5s - 4s
- Memomry Limit : 256MB - 1GB

- Code
- Test the output locally
- Submit

Sometimes instead of reading the problem statement, we can find required logic by observing the pattern in sample input and output. {: .prompt-tip }

### Analyzing given constraints

Conventionally, we can perform 4.108 operation in one second.

#### Complexity Table

N | T.C. |
---|---|

1018 | $O(logN)$ |

108 | $O(N)$ |

104 | $O(N^2)$ |

107 | $O(N \cdot logN)$ |

102 | $O(N^3)$ |

90 | $O(N^4)$ |

20 | $O(2^N)$ |

11 | $O(N!)$ |

### Possible verdicts

- Accpeted
- Time limit Exceeded
- Memory Limit Exceeded
- Compilation Error
- SIGTSTP/SIGSTOP
- Input/Output error.
- Giving instruction which is not implemented in GNU library.

- Runtime Error
- Divinding by zero
- Segmentation Fault
- Memory allocation
- Verify you are indeed returning the answer.
- Re-evaluate the base case of the recursive func.
- Accessing -ve indices
- Declaring global array greater than 108
- Declaring local array greater than 106(4M mem limit per function)

- Wrong Answer
- Work for corner cases.
- Implicit conversion.
- Precision error for float and double.
- Using uninitialized variables.