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

• Fixed Space Requirements (C)
  Independent of the characteristics of the inputs and outputs

  • instruction space

    space for simple variables, fixed-size structured variable, constants

• Variable Space Requirements (SP(I))
  depend on the instance characteristic I

  • number, size, values of inputs and outputs associated with I

    recursive stack space, formal parameters, local variables, return address

投影片 8 之 30