DAA MIDTERM

• Space Efficiency or Complexity


  It is the amount of computer space or memory required by an algorithm (including the input values of the algorithm) to complete its execution and produce the result.
• Instruction space


  It is the amount of memory used to store a compiled version of instructions.
• Data space


  It is the amount of memory used to store all the variables and onstants.
• Run-time Stack Space/Environmental Stack


  It is the amount of memory used to store information of

  partially euted functions at the time of function call.
• T(n)


  It is the amount of computer time required by each operation to execute.
• Cop


  It is the amount of computer time required for a single operation in each line.
• C(n)


  It is the amount of computer time required by each operation for all its repetitions.
• Asymptotic Notations


  These are a set of languages that allow us to analyze an algorithm's running time for asymptotic analysis by identifying its behavior as the input size for the algorithm increases.
• Big-0 Notation


  used to describe the asymptotic upper-bound on growth rate or the worst case of an algorithm in terms of time complexity by taking the highest order of a polynomial function and ignoring all the constants value since they are not that influential for sufficiently large input.
• Constant


  The operation takes the same amount of time, no matter how much data we are dealing with.
• Logarithmic


  The time taken by the operation increases with the size of the data set
• Linear


  The operation is performed n amount of times.
• Quadratic


  The operation is performed n * n times.
• Exponential


  The time taken by the operation gets n times bigger with every additional input
• tractable.


  A problem that can be solved with polynomial worst-case complexity
• intractable.


  Problems of higher complexity
• Big-omega Notation (Ω)


  This notation is used to describe the asymptotic lower-bound on growth rate or the best case of an algorithm in terms of time complexity.
• Big-Theta Notation (Θ)


  This notation is used to describe asymptotic tight bound for it bounds a function from above and below.