# DSA Part 1: Introduction

Posted on Dec 25, 2020

## 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.

## 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

NT.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)