# Algorithm Complexity > Understanding Big O notation, time and space complexity analysis, and performance optimization techniques - **Canonical URL:** https://flashcards.world/flashcards/sets/bf86855c-b9f3-43e2-a152-4af357ccd19f/ - **Markdown URL:** https://flashcards.world/flashcards/sets/bf86855c-b9f3-43e2-a152-4af357ccd19f.md - **Level:** intermediate - **Languages:** en → en - **Total Cards:** 49 ## Flashcards (49 Cards) | # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options | | :--- | :--- | :--- | :--- | :--- | | 1 | What is the time complexity of insertion sort? | The time complexity of insertion sort is O(n^2) in the worst case, but O(n) in the best case when the array is already sorted. | | | | 2 | What does O(log n) signify in algorithm complexity? | O(log n) signifies logarithmic time complexity, meaning the algorithm's running time grows logarithmically as the input size increases. | | | | 3 | What is a data structure? | A data structure is a way of organizing and storing data to enable efficient access and modification. | | | | 4 | What is the average time complexity for searching in a hash table? | The average time complexity for searching in a hash table is O(1), assuming a good hash function with minimal collisions. | | | | 5 | What is the time complexity of radix sort? | 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. | | | | 6 | What is the impact of input size on algorithm performance? | As input size increases, the performance of algorithms can degrade, especially those with higher time complexities. | | | | 7 | What is the difference between time complexity and space complexity? | Time complexity measures the time an algorithm takes to run, while space complexity measures the amount of memory it uses. | | | | 8 | What is time complexity? | Time complexity measures the amount of time an algorithm takes to complete as a function of the length of the input. | | | | 9 | What is the time complexity of selection sort? | The time complexity of selection sort is O(n^2), regardless of the initial order of elements. | | | | 10 | What is the time complexity of a binary search algorithm? | The time complexity of a binary search algorithm is O(log n), where n is the number of elements in the sorted list. | | | | 11 | What is the time complexity of breadth-first search (BFS) in a graph? | The time complexity of breadth-first search (BFS) is O(V + E), where V is the number of vertices and E is the number of edges. | | | | 12 | What is a greedy algorithm? | A greedy algorithm builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. | | | | 13 | What is the time complexity of a merge sort algorithm? | The time complexity of a merge sort algorithm is O(n log n), where n is the number of elements to be sorted. | | | | 14 | What does Big O notation represent? | Big O notation is a mathematical notation used to describe the upper bound of an algorithm's running time or space requirements in terms of the size of the input. | | | | 15 | What is a brute force algorithm? | A brute force algorithm solves a problem by trying all possible solutions until the correct one is found, often resulting in high time complexity. | | | | 16 | What is the time complexity of bubble sort? | The time complexity of bubble sort is O(n^2), where n is the number of elements to be sorted. | | | | 17 | What does O(1) signify in algorithm complexity? | O(1) signifies constant time complexity, meaning the algorithm's running time does not change with the size of the input. | | | | 18 | What is the time complexity of inserting an element in a linked list? | The time complexity of inserting an element in a linked list is O(1) if the position is known, otherwise O(n) if traversal is required. | | | | 19 | What is the time complexity of inserting an element into a sorted array? | The time complexity of inserting an element into a sorted array is O(n), as elements may need to be shifted to maintain order. | | | | 20 | What is the significance of the 'O' in Big O notation? | 'O' stands for 'order of' and indicates the growth rate of an algorithm's complexity relative to the input size. | | | | 21 | How does recursion affect time complexity? | Recursion can increase time complexity, especially if the same subproblems are solved multiple times, leading to exponential growth in running time. | | | | 22 | What is a balanced binary search tree? | A balanced binary search tree is a binary tree where the depth of the two subtrees of every node never differs by more than one, ensuring O(log n) time complexity for operations. | | | | 23 | What is space complexity? | Space complexity measures the amount of memory space an algorithm uses as a function of the length of the input. | | | | 24 | What is the purpose of performance optimization? | Performance optimization aims to improve the efficiency of an algorithm, reducing its time and/or space complexity. | | | | 25 | What is asymptotic analysis? | Asymptotic analysis is the study of the behavior of algorithms as the input size approaches infinity, focusing on the growth rates of time and space complexities. | | | | 26 | What is the space complexity of a recursive algorithm? | The space complexity of a recursive algorithm is O(n), where n is the depth of the recursion stack. | | | | 27 | What is NP-completeness? | NP-completeness is a class of problems for which no known polynomial-time solution exists, but if a solution is provided, it can be verified in polynomial time. | | | | 28 | What is the average-case complexity? | Average-case complexity is the expected time or space an algorithm will take, averaged over all possible inputs. | | | | 29 | What is the worst-case scenario in algorithm analysis? | The worst-case scenario refers to the maximum time or space an algorithm could take to complete, given the most unfavorable input. | | | | 30 | What is algorithm complexity? | Algorithm complexity refers to the quantitative measure of the amount of resources (time and space) that an algorithm consumes as a function of the size of the input data. | | | | 31 | What is the difference between average-case and worst-case complexity? | Average-case complexity considers the expected performance over all inputs, while worst-case complexity considers the maximum performance for the least favorable input. | | | | 32 | What is the purpose of algorithm optimization? | Algorithm optimization aims to improve the efficiency of algorithms, reducing their time and space complexity for better performance. | | | | 33 | What is the time complexity of finding the maximum element in an unsorted array? | The time complexity of finding the maximum element in an unsorted array is O(n), as each element must be checked. | | | | 34 | What is the time complexity of deleting an element from a binary search tree? | The time complexity of deleting an element from a binary search tree is O(h), where h is the height of the tree. | | | | 35 | What does O(n^2) signify in algorithm complexity? | O(n^2) signifies quadratic time complexity, meaning the algorithm's running time grows proportionally to the square of the input size. | | | | 36 | What is the time complexity of depth-first search (DFS) in a graph? | 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. | | | | 37 | What is the time complexity of a linear search algorithm? | The time complexity of a linear search algorithm is O(n), where n is the number of elements in the list. | | | | 38 | What is the role of algorithm analysis? | Algorithm analysis helps in understanding the efficiency of algorithms, guiding the selection of the most appropriate algorithm for a given problem. | | | | 39 | What is an exponential time algorithm? | An exponential time algorithm is one whose time complexity can be expressed as O(2^n), indicating it becomes impractical for large inputs. | | | | 40 | What is the time complexity of a quicksort algorithm? | The average time complexity of a quicksort algorithm is O(n log n), but its worst-case complexity is O(n^2). | | | | 41 | What is a hash table? | A hash table is a data structure that implements an associative array, allowing for fast data retrieval based on keys. | | | | 42 | What is the time complexity of counting sort? | 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. | | | | 43 | What is the time complexity of the Sieve of Eratosthenes? | The time complexity of the Sieve of Eratosthenes is O(n log log n), where n is the upper limit of the range of numbers to find primes. | | | | 44 | What is the significance of the Master Theorem? | The Master Theorem provides a method for analyzing the time complexity of divide-and-conquer algorithms. | | | | 45 | What is a polynomial time algorithm? | A polynomial time algorithm is one whose time complexity can be expressed as O(n^k) for some constant k, indicating it is efficient for large inputs. | | | | 46 | What is the time complexity of accessing an element in an array? | The time complexity of accessing an element in an array is O(1), as it can be done in constant time. | | | | 47 | What is a recursive algorithm? | A recursive algorithm is one that solves a problem by calling itself with a smaller input until a base case is reached. | | | | 48 | What is the best-case scenario in algorithm analysis? | The best-case scenario refers to the minimum time or space an algorithm could take to complete, given the most favorable input. | | | | 49 | What is memoization? | Memoization is an optimization technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again. | | | --- Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/bf86855c-b9f3-43e2-a152-4af357ccd19f/).