Solution

Solution

Time complexity measures how the running time of an algorithm increases as the size of the input data grows. Big O notation gives an upper bound on that time. Examples:

• $O(1)$: constant time; runtime does not depend on input size.
• $O(n)$: linear time, as in searching a list of $n$ students.
• $O(n^{2})$: quadratic time, as in comparing every pair of $n$ students, or Bubble Sort and Selection Sort.
• $O(\log n)$: logarithmic time, as in Binary Search.
• $O(n \log n)$: as in Merge Sort and Quick Sort.
• $O(V + E)$: as in BFS and DFS on a graph.

Space complexity measures how the amount of memory an algorithm uses changes as the input size increases. If an algorithm must store a list of numbers, space complexity describes how much memory is needed as the volume of numbers grows. DFS is described as more memory-efficient for deep graphs, while BFS (which uses a queue of a whole level) is more suited to shallow graphs.

How they affect the choice of algorithm

• For large inputs, prefer a better time bound: Binary Search ($O(\log n)$) over Linear Search ($O(n)$) when the list is sorted; Merge Sort ($O(n \log n)$) over Bubble Sort ($O(n^{2})$).
• If memory is limited, an algorithm with lower space complexity may be chosen even if it is a little slower (for example DFS rather than BFS on a very deep graph).
• If the problem is intractable (super-polynomial time, such as exact TSP for many cities), an exact algorithm may be abandoned in favour of a heuristic or approximation.
• Both measures are used together in algorithm analysis so that the selected algorithm is efficient enough in time and practical in memory for the expected input size.