Cost Using Order notation Worst case time T is proportional to number of nodes visited evel 1 b*1 b*b Level 2 Order Notation ·T=Oe)ifT≤c* e for some constant c Ts=[bm+…b+lcds O(bm) for large b O(bm+) more conservatively Sian willams, Spring o3 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited Level 0 Level 2 ○○(db*b Sado doodad b* Tas=bmt Tas=[bm-1][b-1]*c where caf is time per node williams, Spring a34 Brian Williams, Spring 03 12 Cost Using Order Notation Worst case time T is proportional to number of nodes visited Level 1 Level 2 Level 0 b*1 b*b b*bm-1 . . . Order Notation • T = O(e) if T ≤ c * e for some constant c Tdfs = [bm + … b + 1]*cdfs = O(bm) for large b = O(bm+1) more conservatively 1 Brian Williams, Spring 03 13 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited Tdfs = bm + … b + 1 b * Tdfs = bm+1 + bm + … b Solve recurrence [b – 1] * Tdfs = bm+1 – 1 Tdfs = [bm+1 – 1] / [b – 1] *cdfs where cdfs is time per node Level 1 Level 2 Level 0 b*1 b*b b*bm-1 . . . Level m 1