Computational Time Complexity
Understanding how to analyze and evaluate the efficiency of computational solutions in terms of time and resource requirements
- Category
- Computational Thinking
- Level
- advanced
- Languages
- en → en
- Cards
- 48
- Markdown
- Computational Time Complexity (.md)
Flashcards (48)
| # | Front (Term / Question) | Back (Definition / Answer) | Example | Multiple-Choice Options |
|---|---|---|---|---|
| 1 | What is the time complexity of Strassen's algorithm for matrix multiplication? | The time complexity of Strassen's algorithm for matrix multiplication is approximately O(n^2.81), which is more efficient than the naive approach. | ||
| 2 | What is the purpose of analyzing time complexity? | Analyzing time complexity helps to evaluate the efficiency of algorithms, allowing developers to choose the most suitable one for a given problem. | ||
| 3 | What is the time complexity of the Bellman-Ford algorithm? | The time complexity of the Bellman-Ford algorithm is O(VE), where V is the number of vertices and E is the number of edges. | ||
| 4 | What is the time complexity of the Rabin-Karp algorithm for string matching? | The average time complexity of the Rabin-Karp algorithm is O(n + m), where n is the length of the text and m is the length of the pattern. | ||
| 5 | What is the time complexity of merge sort? | The time complexity of merge sort is O(n log n) in all cases, making it efficient for large datasets. | ||
| 6 | What is the time complexity of binary search? | The time complexity of binary search is O(log n), as it divides the search space in half with each step. | ||
| 7 | What is a greedy algorithm? | A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most immediate benefit. | ||
| 8 | What is the time complexity of Dijkstra's algorithm? | The time complexity of Dijkstra's algorithm is O(V^2) with a simple array, or O(E + V log V) with a priority queue. | ||
| 9 | What is the time complexity of searching in a hash table? | The average time complexity of searching in a hash table is O(1), but it can degrade to O(n) in the worst case due to collisions. | ||
| 10 | What is the time complexity of the A* search algorithm? | The time complexity of the A* search algorithm is O(b^d), where b is the branching factor and d is the depth of the solution. | ||
| 11 | What is the relationship between time complexity and space complexity? | Time complexity and space complexity often trade off; optimizing one may lead to increased usage of the other. | ||
| 12 | What is the significance of P vs NP problem in time complexity? | The P vs NP problem questions whether every problem whose solution can be verified quickly (in polynomial time) can also be solved quickly. | ||
| 13 | What is constant time complexity? | Constant time complexity, denoted as O(1), indicates that the algorithm's running time does not change with the size of the input. | ||
| 14 | What is the time complexity of matrix multiplication using the naive approach? | The time complexity of matrix multiplication using the naive approach is O(n^3), where n is the dimension of the matrices. | ||
| 15 | What is a polynomial time algorithm? | A polynomial time algorithm is one whose time complexity can be expressed as a polynomial function of the input size, typically denoted as O(n^k) for some constant k. | ||
| 16 | What does Big Theta notation represent? | Big Theta notation represents a tight bound on the time complexity, indicating both the upper and lower bounds. | ||
| 17 | What is the time complexity of nested loops? | The time complexity of nested loops is the product of their individual complexities, often resulting in O(n^2) for two nested loops iterating n times. | ||
| 18 | What is quadratic time complexity? | Quadratic time complexity, denoted as O(n^2), indicates that the algorithm's running time is proportional to the square of the size of the input. | ||
| 19 | What is the time complexity of insertion in a balanced binary search tree? | The time complexity of insertion in a balanced binary search tree is O(log n). | ||
| 20 | What is the time complexity of the Floyd-Warshall algorithm? | The time complexity of the Floyd-Warshall algorithm is O(V^3), where V is the number of vertices. | ||
| 21 | How does recursion affect time complexity? | Recursion can lead to increased time complexity due to repeated calculations unless optimized with techniques like memoization. | ||
| 22 | What is the time complexity of breadth-first search (BFS)? | The time complexity of breadth-first search (BFS) is O(V + E), similar to DFS. | ||
| 23 | What is the time complexity of the quickselect algorithm? | The average time complexity of the quickselect algorithm is O(n), while the worst case is O(n^2) if poor pivot choices are made. | ||
| 24 | What is the time complexity of sorting algorithms like quicksort? | The average time complexity of quicksort is O(n log n), while the worst case is O(n^2) if the pivot selection is poor. | ||
| 25 | What is the time complexity of the Prim's algorithm for minimum spanning tree? | The time complexity of Prim's algorithm is O(E log V) when implemented with a priority queue. | ||
| 26 | What is linear time complexity? | Linear time complexity, denoted as O(n), indicates that the algorithm's running time increases linearly with the size of the input. | ||
| 27 | What is amortized time complexity? | Amortized time complexity averages the time taken by a sequence of operations over all operations, providing a more accurate measure for algorithms with occasional expensive operations. | ||
| 28 | What is the time complexity of the radix sort algorithm? | The time complexity of radix sort is O(nk), where n is the number of elements and k is the number of digits in the largest number. | ||
| 29 | What is the time complexity of the Knapsack problem using dynamic programming? | The time complexity of the Knapsack problem using dynamic programming is O(nW), where n is the number of items and W is the maximum weight capacity. | ||
| 30 | What is the difference between best, worst, and average case time complexity? | Best case time complexity describes the minimum time required, worst case describes the maximum time, and average case describes the expected time over all inputs. | ||
| 31 | What is a recursive algorithm? | A recursive algorithm is one that solves a problem by solving smaller instances of the same problem, often using a base case to terminate recursion. | ||
| 32 | What is the time complexity of the counting sort algorithm? | The time complexity of counting sort is O(n + k), where n is the number of elements and k is the range of the input values. | ||
| 33 | What is the time complexity of the topological sorting algorithm? | The time complexity of topological sorting using Kahn's algorithm or DFS is O(V + E), where V is the number of vertices and E is the number of edges. | ||
| 34 | What are the common notations used to express time complexity? | The common notations are Big O (O), Big Theta (Θ), and Big Omega (Ω). | ||
| 35 | What is space complexity? | Space complexity measures the amount of memory an algorithm uses in relation to the input size. | ||
| 36 | What is time complexity in computer science? | Time complexity is a computational concept that describes the amount of time an algorithm takes to complete as a function of the length of the input. | ||
| 37 | What is a heuristic algorithm? | A heuristic algorithm is a problem-solving method that uses practical approaches and shortcuts to produce solutions that may not be optimal but are sufficient for immediate goals. | ||
| 38 | What is the time complexity of bubble sort? | The time complexity of bubble sort is O(n^2) in the worst and average cases, and O(n) in the best case when the array is already sorted. | ||
| 39 | What does Big O notation represent? | Big O notation represents the upper bound of an algorithm's time complexity, indicating the worst-case scenario. | ||
| 40 | What is the time complexity of a simple loop that iterates n times? | The time complexity of a simple loop that iterates n times is O(n). | ||
| 41 | What does Big Omega notation represent? | Big Omega notation represents the lower bound of an algorithm's time complexity, indicating the best-case scenario. | ||
| 42 | What is the time complexity of a linear search? | The time complexity of a linear search is O(n), as it checks each element in the list sequentially. | ||
| 43 | What is an exponential time algorithm? | An exponential time algorithm is one whose time complexity grows exponentially with the input size, typically denoted as O(2^n). | ||
| 44 | What is the time complexity of the Sieve of Eratosthenes for finding prime numbers? | The time complexity of the Sieve of Eratosthenes is O(n log log n), making it efficient for generating all prime numbers up to n. | ||
| 45 | What is logarithmic time complexity? | Logarithmic time complexity, denoted as O(log n), indicates that the algorithm's running time increases logarithmically as the input size increases. | ||
| 46 | What is the significance of the Master Theorem in time complexity analysis? | The Master Theorem provides a method for analyzing the time complexity of divide-and-conquer algorithms. | ||
| 47 | What is the time complexity of depth-first search (DFS)? | The time complexity of depth-first search (DFS) is O(V + E), where V is the number of vertices and E is the number of edges. | ||
| 48 | What is the time complexity of the Kruskal's algorithm for minimum spanning tree? | The time complexity of Kruskal's algorithm is O(E log E) or O(E log V), where E is the number of edges and V is the number of vertices. |