Algorithms 2.3 Flashcards
What is time complexity?
The amount of time required to solve a problem
What is space complexity?
The amount of storage space an algorithm takes up
What is the time complexity for a linear search?
O(n)
What is the time complexity for a binary search?
o(logn)
What is the time complexity for bubble sort?
o(n^2)
What is the time complexity for insertion sort?
o(n^2)
What is the time complexity of a merge sort algorithm?
O(nlogn)
What is the time complexity of a quicksort algorithm?
O(nlogn)
What is a condition of a binary search tree?
All data must be storted(ordered)
What is Dijsktra’s algorithm?
A shortest path algorithm used to find the shortest distance between two nodes in a network
How is Dijkstra’s algorithm implemented?
Use a priority queue which has the shortest lengths at the begining
What is the A* algorithm?
A pathfinding algorithm which has two costs; actual cost and aproximated cost
Why are heuristics used in the A* algorithm?
To calculate an approixmate cost from node x to the destination node. It aims to find the shortest path
State a disadvantage of the A* algorithm
It takes a large amount of space to store all possible paths and a lot of time to find them
State a disadvantage of the Dijkstra algorithm
It does a blind search there by consuming a lot of time waste of necessary resources
