Searching Algorithms Flashcards
What is a linear sort?
When the items are not in any particular order, the data items have to be searched one by one until the required one is found or the end of the list is reached
What is the time complexity of the linear search, in Big-O notation?
O(n)
What is the precondition of a binary search?
The item in the list must be sorted
How does a binary search work?
It repeatedly divides the portion of the data list that could contain the require data item, this is continued until there is only one item in the list
What is the time complexity of a binary search, in terms of Big O notation?
O(log n)
What is the binary search strategy?
Divide and conquer
How is a binary tree search done?
Similar to a binary tree, but instead of removing half of the list ,it eliminates a subtree each time its root is examined
What is the time complexity if binary tree search, in terms of Big-O notation?
Same as a binary search O(log n)
