Section 8 Chapter 46 and 47
No description yet. This curated deck is ready for daily study.
Card preview (15)
Linear search
Searching for an object in a list by checking each object in order until the desired object is found
Linear search complexity
O(n)
Why you would use a linear search
To search an unordered list
Time complexity of binary search
O(log n)
Time complexity of bubble sort
O(n^2)
Time complexity of merge sort
O(nlog n)
What merge sort and binary search are examples of
Divide and conquer
Space complexity
The amount of resources, for instance memory, that an algorithm requires
How to code depth first search
Recursion
How to code breadth first search
Just do it in a function, use a queue and when adding, check that the node is not in visited AND not in the queue
Application of depth first search
Navigating through a maze
Applications of breadth first search (2)
• Finding the shortest path between two nodes - Web crawlers going through links
Data structure associated with a depth first search
stack
Data structure associated with a breadth first search
queue
What traversal is the same as the depth first search
pre order