Search Algorithm Run Time

Binary Search

最基本的二分查找法。the worst-case running time of binary search is Θ(logn). 因为你每次可以过滤掉总Array一半的elements，所以基本就是你总共可以把array size除2的次数。

A* Search

Uniform Search

表示Graph，一般都是用Adjacency List. 

BFS

Overall Running time: O(|V|+|E|). 因为一共有2|V|次queue operations. 放进queue一次，pop出一次。然后对于每一个vertex，都会loop scan each edge 一次， 所以O(|E|).

Therefore, Overall Running time: O(|V|+|E|

DFS

每个Vertex都会去一次，每次到一个vertex，我们需要标记一下这个visited了. 一次标记是O(1). |V|次就是O(|V|).   

然后每次在一个vertex标记完这里已经来过了以后， 扫描一下这个vertex的adjacent edges， 看看能不能去到一个新的node。【比如去到其child vertex】. 

这一步总的runtime为O(|E|), 因为衣柜最多也就看|E| 个edges。所以DFS的总时间是O(|V|+|E|)

Dijkstra

Dijkstra 算法很像BFS，但是慢了一些因为用了PriorityQueue。由于Priority Queue有很多种不同的implementation，所以不同的implementation会导致不同的Run Time。