 by Priyanshu Tiwari

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

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