CODEWITHSUNDEEP
pythonperformancememory
Taztingo
Taztingo

Reputation: 1945

Basic DFS space usage

I have a basic question related to space usage, and I'm using DFS as an example. I'm not sure if the space usage in these few implementations are the same, or if a few actually differ. My interpretation of space usage is directly correlated to what the function allocates. Can anyone help me verify the space usage of these few examples I made? This is a question on space complexity, and not time + functionality

Example 1: We allocate a dictionary that will store N nodes. I'm positive this one allocates O(N) space.

class Node:
    def __init__(self, children):
        self.children = children

    def getChildren(self):
        return self.children

def dfs(start):
    stack = []
    visited = {}
    stack.append(start)
    while(len(stack) > 0):
        node = stack.pop()
        if(node not in visited):
            visited[node] = True
            for child in node.getChildren():
                stack.append(child)

Example 2: We don't allocate anything in the dfs function, but instead we are given a flag to set on the Node. We aren't allocating anything in the dfs function so it is O(1) space usage.

class Node:
    def __init__(self, children):
        self.children = children
        self.visited = False

    def getChildren(self):
        return self.children

    def getVisited(self):
        return self.visited

    def setVisited(self, visit):
        self.visited = visit

def dfs(start):
        stack = []
        stack.append(start)
        while(len(stack) > 0):
            node = stack.pop()
            if(!node.getVisited()):
                node.setVisited(True)
                for child in node.getChildren():
                    stack.append(child)

Example 3: We have an object Node that can be manipulated, but does not have a flag attribute up front. DFS is manually creating a flag on each Node, and thus allocating O(N) space. 

class Node:
    def __init__(self, children):
        self.children = children

    def getChildren(self):
        return self.children

def dfs(start):
    stack = []
    stack.append(start)
    while(len(stack) > 0):
        node = stack.pop()
        if(node.visited is not None):
            node.visited = True
            for child in node.getChildren():
                stack.append(child)

Upvotes: 0

Views: 236

Answers (1)

miraculixx
miraculixx

Reputation: 10379

Space complexity is not determined by where the space gets allocated but by how much space (memory) is required to hold a given data structure in relation to the number of objects to be processed by an algorithm.

In your examples all data structures require O(N) space (N = # of nodes)

Upvotes: 1

Related Questions