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.

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

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)
  • Wrong Answer
    • Work for corner cases.
    • Implicit conversion.
    • Precision error for float and double.
    • Using uninitialized variables.