1.2.1 Space and time complexity

1.2.1. Time Complexity:

• The time needed by an algorithm expressed as a function of the size of a problem is called the TIME COMPLEXITY of the algorithm. The time complexity of a program is the amount of computer time it needs to run to completion.
• The limiting behavior of the complexity as size increases is called the asymptotic time complexity. It is the asymptotic complexity of an algorithm, which ultimately determines the size of problems that can be solved by the algorithm.
• Generally, running time of an algorithm depends upon the following...

1. Whether it is running on Single processor machine or Multiprocessor machine.
2. Whether it is a 32-bit machine or 64-bit machine
3. Read and Write speed of the machine.
4. The time it takes to perform Arithmetic operations, logical operations, return value and assignment operations etc.
5. Input data

Space Complexity: 

The space complexity of a program is the amount of memory it needs to run to completion. The space need by a program has the following components: 

• Instruction space: Instruction space is the space needed to store the compiled version of the program instructions. 
• Data space: Data space is the space needed to store all constant and variable values. Data space has two components:
• Space needed by constants and simple variables in program.
• Space needed by dynamically allocated objects such as arrays and class instances.
• Environment stack space: The environment stack is used to save information needed to resume execution of partially completed functions.
• Instruction Space: The amount of instructions space that is needed depends on factors such as:

• The compiler used to complete the program into machine code.
• The compiler options in effect at the time of compilation
• The target computer.

Space Complexity S(P)= C + SP(I)

Fixed space requirements(C) independent of the i/p and o/p.

• Instruction space. 
• Space for simple variables, fixed size structured variable, constants.

Variable space requirements SP(I) depend on the instance characteristics I

• Number, Size, values of inputs and outputs associated with I.
• Recursive stack space, formal parameters, local variable, return address.

Asymptotic Notations

When we calculate complexity of an algorithm it does not provide exact amount of resource required. So instead of taking exact amount of resource we represent that complexity in a general form (Notation) which produces the basic nature of that algorithm. We use that general form (Notation) for analysis process.

Definition- Asymptotic notation of an algorithm is a mathematical representation of its complexity. 

Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm.

1. Ο Notation
2. Ω Notation
3. θ Notation