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.