Elements of Algorithmic analysis · Soundness is a solution returned by the algorithm guaranteed to be Completeness is the algorithm guaranteed to find a solution when there is Time complexity how long does it take to find a solution? Space complexity how much memory does it need to perform search? Sian willams, Spring o3 Characterizing Search algorithms Level o Level 1 Level 2 b= maximum branching factor, number of children d= depth of the shallowest goal node m= maximum length of any path in the state space williams, Spring a32 Brian Williams, Spring 03 8 Elements of Algorithmic Analysis • Soundness: – is a solution returned by the algorithm guaranteed to be correct? • Completeness: – is the algorithm guaranteed to find a solution when there is one? • Time complexity: – how long does it take to find a solution? • Space complexity: – how much memory does it need to perform search? Brian Williams, Spring 03 9 Characterizing Search Algorithms d = 1 Level 1 Level 2 Level 0 b = 3 b = maximum branching factor, number of children d = depth of the shallowest goal node m = maximum length of any path in the state space m = 1