Priyanshu Tiwari
by Priyanshu Tiwari
2 min read

Categories

Tags

Table Of Content

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.

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.