While introducing algorithms we talked about assessing algorithms through their efficiency, now we will explore how we can evaluate the efficiency of algorithms. This gives us a metric to understand whether we are improving our algorithm.
There are two metrics we evaluate, time complexity and space complexity, ideally, we want our algorithm to be best at both, but it is not always possible. With the rise of mega storages, space complexity is the one usually traded off, still, we have limited resources. Space complexity or memory required is divided further as input space (memory required to store the input) and auxiliary space (memory required to execute the algorithm), of which input space is less of in-control of an algorithm designer, so we will talk more about auxiliary space. There can be different approaches to reduce auxiliary space requirements. Sometimes use of functional programming may help reduce memory usage significantly, minimizing redundancy or copying or use of variables, or using mutable data structures, these are some of it. Even the tiniest bit of improvement in theory can be crucial in practice, when it comes to scaling.
Time complexity has a bigger share in assessing the quality of an algorithm. Where we theoretically analyze how many computations
will an algorithm take given an input of size n, for that we have a set of computations as fundamentals, base cases each of which
takes constant amount of time. Usually these computations/instructions are arithmetic (add, subtract, multiply, divide, remainder,
floor, ceiling), data movement (load, store, copy) and control (conditional instructions, subroutine calls and return statements).
We analyze algorithms for best case, worst case and average case.
For this section we assume function f(n) represents the algorithm's time-complexity as a function of input size n. And g(n) is a function that defines bounds to our function f(n).
Θ-notation: for g(n), Θ(g(n)) = f(n) denotes a set of functions {g(n)}, such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all n≥n0.
This is called as an asymptotically tight bound, so f(n) never escapes the space covered by {g(n)}, which makes us easier to analyse our algorithm.
O-notation: it is not always possible to find an asymptotic tight bound for our function f(n), i.e. a bound on both ends, so O(g(n)) = f(n) denotes the asymptotic upper bound, i.e. set {g(n)}, s.t. 0 ≤ f(n) ≤ c g(n) for all n ≥ n0, this helps us analyze the worst case scenario of the algorithm.
Ω-notation: similar to previous case, Ω provides us with the asymptotic lower bound, i.e. set {g(n)}, s.t. 0 ≤ c g(n) ≤ f(n) for all n ≥ n0, which helps us analyze the best case scenario of an algorithm
Predominantly, in practice O-notation is hugely exploited, which you may notice in almost every blog article.
Now, with some basic information in hand lets try to understand time-complexity of an example algorithm. Let us consider a psuedo-code for python,
Remove duplicates
Remove_duplicates(arr): 1.
unique = {} # create an empty set 2.
for element in arr: 3.
unique.append(element) 4.
return unique 5.
This algorithm works with time-complexity of O(n) and auxiliary space of O(n) for storing the set unique. Let's analyze how time complexity of O(n) is evaluated,
with fundamental operations in mind which takes constant O(1) to run, lines 1,5 directly take O(1) or constant amount of time to execute, and so does creating an empty set in line 2.
Lines 3 and 4 also take constant time, but are executed n times, for each element in arr. Combining all takes, O(1) + O(1) + n + n + O(1) = 2n + 3 O(1) amount of time, while evaluating with notations
the constant factors with n are often neglected unless for a deep theoretical analysis, typically in cases where two or more algorithms take same O(variable) time and we have to find best one,
in such cases the constant factor carries high importance, but for our purpose we need not go there, and terms with lower polynomial order are also neglected, hence our algorithm could be stated to take O(n) of time or precisely Θ(n) time.
Sets carry a property to carry unique elements only, which is implemented using a concept of hash function, which for a given element directly gives us an address of element in the table, making search of element
in constant O(1) time, on average. This algorithm has best case, worst case, and average case time complexity of O(n). As seen in this example, we evaluate the time complexity of our algorithm as a function of our fundamental operations.
8 Feb 2024.
Next in series: Divide and Conquer.