AP CSP algorithm efficiency and undecidable problems cheat sheet
This cheat sheet covers key concepts of algorithm efficiency, including Big O notation, time complexity, and undecidable problems relevant for AP Computer Science Principles.
Quiz(56 questions)
1. What does algorithm efficiency primarily measure?
Terms in this Study Set(56)
Algorithm Efficiency(20)
Define Algorithm Efficiency.
Algorithm efficiency measures the resources required (time and space) for an algorithm to complete. It evaluates how quickly an algorithm runs and how much memory it uses.
What is time complexity?
Time complexity quantifies the amount of time an algorithm takes to complete as a function of the input size, often expressed using Big O notation.
True or False: A linear algorithm is O(n^2).
False. A linear algorithm is O(n), meaning its time complexity grows linearly with the input size.
Fill in the blank: The worst-case time complexity of a binary search is ____.
O(log n). This reflects that with each comparison, the search space is halved.
Compare Linear Search and Binary Search.
- Linear Search: O(n) time complexity. - Binary Search: O(log n) time complexity (requires sorted array).
What does the term 'space complexity' refer to?
Space complexity measures the total memory space an algorithm requires, including both the input size and auxiliary space used during execution.
What is the time complexity of bubble sort?
Bubble sort has a time complexity of O(n^2) in the worst and average case scenarios due to nested iterations.
What is the average case of quicksort?
O(n log n). Quicksort is efficient for large datasets, as it divides the array into partitions.
True or False: Recursive algorithms always have better efficiency than iterative ones.
False. Recursion can add overhead and may use more space due to call stack.
Define polynomial time.
Polynomial time refers to an algorithm that runs in O(n^k) for some constant k, indicating efficient scalability with input size.
What is a constant time complexity?
O(1). The execution time remains constant, regardless of the input size.
What is the difference between O(n) and O(n log n)?
O(n) grows linearly with input size, while O(n log n) grows slightly faster due to logarithmic factor.
What is amortized time complexity?
Amortized time complexity averages out the time taken over a sequence of operations, providing a more generalized analysis.
Cause → Effect: What happens when an algorithm has O(n^3) complexity?
The algorithm will perform significantly slower with larger inputs, making it inefficient for large datasets.
True or False: All algorithms have the same efficiency.
False. Algorithms vary widely in efficiency based on their design and the input they process.
What is the impact of input size on algorithm efficiency?
Larger input sizes typically increase execution time and resource usage, affecting overall efficiency.
Fill in the blank: The time complexity for merge sort is ____.
O(n log n). It efficiently divides and conquers the data.
Define exponential time complexity.
Exponential time complexity is O(2^n), indicating that the algorithm's execution time doubles with each additional input element.
What is the time complexity of a for loop that runs n times?
O(n). Each iteration contributes to the total time based on the number of times it runs.
Define logarithmic time complexity.
Logarithmic time complexity, O(log n), occurs when the algorithm reduces the problem size by a constant factor (e.g., halving) with each step, like binary search, making it very efficient for large inputs.
Big O Notation(16)
What does Big O notation describe?
The upper bound of an algorithm's time complexity in the worst-case scenario.
True or False: O(n) is slower than O(log n).
True. O(n) grows linearly, while O(log n) grows logarithmically, which is faster.
O(1) means...
Constant time complexity; execution time does not change with input size.
Fill in the blank: O(n^2) is commonly seen in ________ algorithms.
Quadratic sorting algorithms, like bubble sort and insertion sort.
Compare O(n) and O(n log n).
O(n) is linear; O(n log n) is more complex, typically seen in efficient sorting algorithms.
What is the Big O of this loop: for i from 1 to n, do something?
O(n). The time complexity increases linearly with n.
O(n^3) indicates what type of algorithm?
Cubic time complexity, often found in algorithms with three nested loops.
True or False: O(n) and O(2n) are equivalent.
True. They are both linear; constants do not affect Big O notation.
What is the Big O of an algorithm with nested loops both running n times?
O(n^2). Each loop contributes to the total complexity.
Cause → Effect: Increasing input size in O(n log n) algorithm leads to...
Increased execution time, but more efficiently than O(n^2) algorithms.
What is the best-case time complexity of a linear search?
O(1). If the target is the first element.
Identify the Big O: Merge Sort algorithm.
O(n log n). Efficient sorting using divide and conquer.
True or False: O(log n) indicates exponential growth.
False. O(log n) indicates logarithmic growth, which is slower than linear.
What does O(n!) represent?
Factorial time complexity, typical in algorithms generating permutations.
O(√n) indicates what kind of time complexity?
Sub-linear time complexity; efficiency increases with larger n.
Fill in the blank: The function f(n) = 3n + 2 is O(____).
O(n). Constants are ignored in Big O notation.
Undecidable Problems(12)
What is an undecidable problem?
A decision problem that cannot be solved by any algorithm. Examples include the Halting Problem.
True or False: The Halting Problem is decidable.
False. The Halting Problem is undecidable; no algorithm can determine if any given program halts.
Example of an undecidable problem: __________.
The Halting Problem. It's impossible to determine if a program will eventually stop.
What does the term "reductions" mean in undecidability?
Transforming one problem into another to show that if one is undecidable, so is the other.
Which problem is used to prove undecidability?
The Halting Problem is often used to prove other problems are undecidable.
Can undecidable problems be solved in any specific cases?
Yes, for particular instances, they may be solvable, but not in general.
The Church-Turing Thesis relates to undecidable problems by stating __________.
Any computation can be simulated by a Turing machine, linking undecidable problems to computation.
Example of a decision problem that is undecidable: __________.
The Post Correspondence Problem.
Fill in the blank: If a problem is undecidable, it has no __________ solution.
Algorithmic.
Which class includes problems that are reducible to the Halting Problem?
Undecidable problems class.
True or False: All problems in NP are decidable.
True. NP problems can be solved by a non-deterministic algorithm, and they are decidable.
Compare decidable and undecidable problems.
Decidable: solvable by an algorithm. Undecidable: cannot be solved by any algorithm.
Complexity Classes(8)
P vs NP: Define P.
P is the class of decision problems that can be solved in polynomial time by a deterministic Turing machine.
NP-Complete: What does it mean?
NP-Complete problems are the hardest problems in NP. If one NP-Complete problem can be solved in polynomial time, all NP problems can.
True or False: All NP problems are NP-Complete.
False. Not all NP problems are NP-Complete; NP contains problems that are easier than NP-Complete.
Difference: P vs NP.
- P: Solvable in polynomial time. - NP: Verifiable in polynomial time. - NP-Complete: Most difficult in NP.
Fill in the blank: An NP problem can be solved in __________ time.
non-deterministic polynomial time.
Cause → Effect: If P = NP, then...
...all problems in NP can be solved efficiently, revolutionizing computer science and problem-solving.
Example of NP-Complete problem?
One classic example is the Traveling Salesman Problem (TSP). It requires finding the shortest possible route visiting each city once.
What is the significance of NP-Hard?
NP-Hard problems are at least as hard as the hardest problems in NP. They are not necessarily in NP.
Questions in this Study Set(56)
1. What does algorithm efficiency primarily measure?
2. What does Big O notation primarily measure?
3. What characterizes an undecidable problem?
4. Which of the following statements best defines the class P?
5. How is time complexity typically expressed?
6. Which of the following is true regarding O(1) and O(n)?
7. Which of the following is a classic example of an undecidable problem?
8. Which of the following is true about NP-Complete problems?
9. Which of the following complexities indicates a linear algorithm?
10. Fill in the blank: O(n log n) is often associated with ________ algorithms.
11. True or False: The Halting Problem can be resolved for some specific programs.
12. Which of the following is NOT true regarding NP problems?
13. Fill in the blank: The space complexity of an algorithm includes both ____ and auxiliary space.
14. What is the Big O of a single loop that runs 'n' times?
15. What is the significance of reductions in the context of undecidable problems?
16. What distinguishes NP problems from P problems?
17. Which algorithm typically has the highest average time complexity?
18. Which of the following time complexities indicates the slowest growth?
19. Which of the following is NOT an undecidable problem?
20. If it were proven that P = NP, what would be the implication?
21. What is the time complexity for performing a binary search on a sorted array?
22. If an algorithm has a time complexity of O(n!), it typically involves what kind of computations?
23. What does the Church-Turing Thesis propose about computation?
24. Which of the following is an example of an NP-Complete problem?
25. True or False: A recursive algorithm can have worse efficiency than an iterative algorithm.
26. True or False: O(n^3) time complexity is faster than O(n^2).
27. Which statement about undecidable problems is accurate?
28. Which statement about NP-Hard problems is correct?
29. What is an example of polynomial time complexity?
30. Which scenario would lead to increased execution time in an O(n log n) algorithm?
31. Fill in the blank: An undecidable problem has no __________ solution.
32. What is the significance of NP-Completeness?
33. Which time complexity suggests a constant execution time regardless of input size?
34. What is the time complexity of a nested loop where each loop runs n times?
35. Which of the following problems is known to be undecidable?
36. What is the difference in growth rates between O(n) and O(n log n)?
37. Which of these time complexities is NOT comparable to O(n)?
38. True or False: All problems in the class NP are undecidable.
39. What does amortized time complexity provide?
40. What does O(√n) represent in terms of time complexity?
41. Which best compares decidable and undecidable problems?
42. What happens to an algorithm with O(n^3) complexity as input size increases?
43. True or False: O(2n) is equivalent to O(n).
44. Which of the following statements about the Halting Problem is true?
45. True or False: All algorithms execute with the same efficiency.
46. Identify the Big O notation of the Binary Search algorithm.
47. How does larger input size affect algorithm efficiency?
48. Which of the following correctly describes the relationship between O(n) and O(n^2)?
49. Fill in the blank: Merge sort has a time complexity of ____.
50. What does O(n^2) typically indicate about an algorithm's performance?
51. What characterizes exponential time complexity?
52. Which of the following is NOT a characteristic of O(log n) time complexity?
53. What is the time complexity of a simple for loop that iterates n times?
54. Define logarithmic time complexity.
55. Which of the following scenarios represents an algorithm with logarithmic time complexity?
56. Which of the following describes the time complexity of insertion sort in the worst case?
Related Study Sets
Informatyka studia – Algorytmy i struktury danych
Greedy-Algorithmen Wechselgeldproblem Definitionen
Abiturwissen: Formale Sprachen und Grammatiken
Abitur: Komplexität grob
Endliche Automaten Abiturvorbereitung
Suche linear und binär Karteikarten
Dynamische Programmierung Prüfungsfragen
Sortieren einfach erklärt Karteikarten
Create Your Own Study Set
Upload a PDF, paste your notes, or describe a topic – AI generates flashcards, quizzes and more in seconds.
