Time and Space Complexity

8 flashcards · Computer Science · by J M COOPER

1. Best First space and time complexity

   time: O(bd) space: O(bd)

2. Depth First space and time complexity

   time: O(bd) space: O(bd)

3. Breadth First space and time complexity

   time: O(bd) space: O(bd)

4. A* space and time complexity

   time: O(bd) space: O(bd)

5. What does space complexity mean in terms of search

   The number of things we have to store - e.g. the length of the frontier

6. What does time complexity mean in terms of search

   If you can access a node in O(1), the number of node visits

7. How many rows does a CPT for boolean Xi with k boolean parents have?

   2k

8. If each boolean variable has no more than k boolean parents, how many numbers does the entire network require?

   O(n · 2k)