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)ExampleMultiple-Choice Options
1What 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.
2What 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.
3What 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.
4What 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.
5What 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.
6What 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.
7What is a greedy algorithm?A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most immediate benefit.
8What 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.
9What 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.
10What 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.
11What 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.
12What 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.
13What 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.
14What 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.
15What 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.
16What does Big Theta notation represent?Big Theta notation represents a tight bound on the time complexity, indicating both the upper and lower bounds.
17What 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.
18What 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.
19What 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).
20What 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.
21How does recursion affect time complexity?Recursion can lead to increased time complexity due to repeated calculations unless optimized with techniques like memoization.
22What is the time complexity of breadth-first search (BFS)?The time complexity of breadth-first search (BFS) is O(V + E), similar to DFS.
23What 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.
24What 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.
25What 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.
26What 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.
27What 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.
28What 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.
29What 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.
30What 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.
31What 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.
32What 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.
33What 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.
34What are the common notations used to express time complexity?The common notations are Big O (O), Big Theta (Θ), and Big Omega (Ω).
35What is space complexity?Space complexity measures the amount of memory an algorithm uses in relation to the input size.
36What 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.
37What 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.
38What 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.
39What does Big O notation represent?Big O notation represents the upper bound of an algorithm's time complexity, indicating the worst-case scenario.
40What 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).
41What does Big Omega notation represent?Big Omega notation represents the lower bound of an algorithm's time complexity, indicating the best-case scenario.
42What 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.
43What 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).
44What 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.
45What 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.
46What 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.
47What 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.
48What 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.