Algorithms Flashcards
(13 cards)
What is the purpose of algorithm analysis?
To evaluate the time and space an algorithm uses so we can compare efficiency.
What is Big O notation?
A mathematical way to describe the upper bound of an algorithm’s time or space complexity.
What is O(1) time complexity?
Constant time – the algorithm takes the same time regardless of input size.
What is O(n) time complexity?
Linear time – time grows directly in proportion to input size.
What is O(n²) time complexity?
Polynomial time – time grows proportionally to the square of the input size.
What is O(log n) time complexity?
Logarithmic time – time increases slowly as input size grows.
What is O(2ⁿ) time complexity?
Exponential time – time doubles with each additional input element, very inefficient.
What is Dijkstra’s algorithm used for?
To find the shortest path between two nodes in a weighted graph.
How does Dijkstra’s algorithm work?
It uses a priority queue to repeatedly visit the nearest unvisited node and update shortest path estimates.
What is A* (A-star) algorithm used for?
To find the shortest path efficiently using a heuristic to guide the search.
How does A* differ from Dijkstra’s?
A* adds a heuristic estimate to the total cost, making it faster in many cases.
When is an algorithm suitable for a problem?
When it solves the problem correctly and efficiently for the size and type of data involved.
What factors affect an algorithm’s suitability?
Input size, time complexity, memory usage, and structure of data.
