Big O Notation Flashcards
What is Big O notation?
A way to describe how fast or slow an algorithm is as the size of the input grows.
What does O(1) mean?
Constant time -the algorthim takes the same time as the input grows
What is an example of an O(1) operation?
Accessing an array element by index (e.g., arr[0]).
What does O(n) mean?
Linear time – time grows directly in proportion to input size (n).
Give an example of an O(n) algorithm.
Linear Search or a simple loop (e.g., for i in range(n)).
What does O(log n) mean?
Logarthmic time- takes less time as input grows
Give an example of an O(log n) algorithm.
Binary Search.
What does O(n²) mean?
Quadratic or polynomial time – time grows proportionally to n squared.
Give an example of an O(n²) algorithm.
Bubble Sort or nested loops (for i in range(n): for j in range(n):).
What does O(2ⁿ) mean?
Exponential time – time doubles as input size grows (n).
Give an example of an O(2ⁿ) algorithm.
Recursive Fibonacci or brute-force combinatorics.
What is meant by “worst-case scenario” in Big O?
The algorithm takes the longest possible time for a given input size.
What is algorithm efficiency?
A measure of how well an algorithm performs based on time and space as input size grows.
What is Dijkstra’s algorithm used for?
An algorithm for finding the shortest paths between nodes in a graph
What is A* (A-star) algorithm?
An algorithm that finds the shortest path by using both actual cost and a heuristic to find the most efficient path to the target node.
What is a heuristic in A*?
An estimated cost from the current node to the goal (e.g., Euclidean or Manhattan distance).
What does “admissible heuristic” mean?
A heuristic that never overestimates the minimum cost to reach the goal.
How does A* compare to Dijkstra in terms of performance?
A star is faster ,because the heuristic guides the search more efficiently.
What is meant by “comparing algorithm complexity”?
Evaluating which algorithm is more efficient based on Big O, considering how they scale with larger inputs.
