educative.io

Space complexity of exclusive execution time of functions

Courses
,
#1

The stated time complexity is O(mlog(n+t)), because we process that many characters in the input.

The stated space complexity is O(m), but we store the aforementioned processed characters in our stack. Should the space complexity also be O(mlog(n+t))?

Course: Grokking Coding Interview Patterns in Python - AI-Powered Learning for Developers
Lesson: https://www.educative.io/courses/grokking-coding-interview-patterns-python/solution-exclusive-execution-time-of-functions

1 Like
#2

Hi @Isaac_Haseley,

The space complexity for the logs_stack is O(m) under the following assumptions:

  • Each stack entry consumes a fixed amount of space.
  • The stack grows linearly with the number of unmatched “start” logs, which at maximum would be all m logs if they were all “starts”.

The notion that the space complexity would involve a logarithmic component (such as log(n+t)) typically arises in scenarios where the data structure’s depth or breadth is dependent on the number of elements it contains (like trees, heaps, or hash tables resizing). In the case of a stack, however, each element is pushed and popped in constant space regardless of its content’s numerical value.

Hope this answers your query, thanks!

#3

Hey @Dian_Us_Suqlain!

  • Each stack entry consumes a fixed amount of space.

In Python, stacks (lists) store pointers to objects of arbitrary size, so the total space consumed by a stack includes not just the number of pointers, but also the sizes of the objects they point to.

We can make a simplifying assumption that the size of our log records is fixed. If we do that, should we make that assumption in the time complexity as well, and change that from O(mlog(n+t)) to O(m)?