Flashcards on Computer Science: Algorithms and Complexity
Click on the flashcard to see the answer
What is an algorithm?
A set of instructions or rules to solve a problem or perform a specific task.
What is time complexity?
It measures the amount of time an algorithm takes to run based on the input size.
What is space complexity?
It measures the amount of memory or space an algorithm requires based on the input size.
What is the Big-O notation?
It is used to describe the upper bound or worst-case scenario for the time complexity of an algorithm.
What is the difference between a linear search and a binary search?
A linear search checks every element in a list, while a binary search divides the list in half at every step.
What is a sorting algorithm?
It organizes a list of items in a specific order, such as ascending or descending.
What is a recursive function?
A function that calls itself during its execution.
What is the best-case time complexity?
It describes the optimal scenario for the time complexity of an algorithm.
What is the worst-case time complexity?
It describes the highest possible time complexity of an algorithm.
What is the average-case time complexity?
It describes the expected time complexity of an algorithm based on the average input.
What is the best algorithm to sort a list in ascending order?
Quicksort is considered one of the most efficient sorting algorithms.
What is the worst algorithm to search for an item in a list?
Linear search has the worst time complexity for searching.
What is the purpose of analyzing algorithm complexity?
It helps in understanding the efficiency and performance of an algorithm.
What is the difference between a stack and a queue?
A stack follows LIFO (Last In, First Out) principle, while a queue follows FIFO (First In, First Out) principle.
What is the difference between a breadth-first search and a depth-first search?
Breadth-first search explores all the vertices at the same level before moving to the next level, while depth-first search explores as far as possible along each branch before backtracking.
What is the advantage of using a divide and conquer algorithm?
It breaks a problem into smaller subproblems and solves them independently, leading to efficient solutions.