Swift Programming: Big O notation for complexity checking
Big O Notation: Complexity measurement and optimization for Swift programming
“Big O notation”, a well-known concept in computer science and a must ask topic in any technical round for developer job. If you heard this term for the very first time, no worry, here you will understand what this “Big O notation” all about.“Big O notation” is a general computer science concept, which helps the developer to measure the time and memory space complexity of an algorithm or program block. Measuring complexity is a common practice in a development environment for many causes, like,
- To determine the efficiency of an algorithm (asymptotic analysis).
- To determine the requirement for algorithm optimization.
- Find total execution time for given input data.
- Cost estimation on executing time.
Here “Big O notation” plays a significant role to determine the time and memory complexity of an algorithm, depend upon the given number of inputs or datasets. It helps to understand how the number of inputs affects the number of works to be performed as well as space consumption by a block of code. Mathematically, it is denoted by “Big O notation”, which shows the relationship between the algorithm and the number of inputs to be processed by it. Let’s see what are the different Big O values and their analysis for your Swift programming.
1. O(1) - Constant Time: Probably, the best performance. Regardless of a number of inputs, the operation complexity of O(1) is always constant.
For example,
let anArr = [11, 20, 32, 41, 55, 63]
anArr[1]
anArr[4]
From the above code, you can pick any of the Array elements, by accessing the correct index of. Whether the array has 10 elements or 1000, picking an element from the Array needs constant time to 1. So the complexity is O(1). A similar example of O(1) would be, appending element in an Array or push/pop operation on Stack.
2. O(log n) - Logarithmic Time: Probably, the second-best performance. When dealing with an O(log n) complexity operation, each operation cycle should reduce the complexity in relation to the input. For example,
func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
var lowerBound = 0
var upperBound = a.count
while lowerBound < upperBound {
let midIndex = lowerBound + (upperBound - lowerBound) / 2
if a[midIndex] == key {
return midIndex
} else if a[midIndex] < key {
lowerBound = midIndex + 1
} else {
upperBound = midIndex
}
}
return nil
}
let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
binarySearch(numbers, key: 43)
Consider the above Swift function, a typical binary search on a sorted Array. On every iteration of the While loop, it reduces the number of elements by log2(n). This way, the whole process complexity will be log2(n) of the total number of inputs n.
Mathematically, say, we have a total of 100 elements for binary search, then the complexity would be log2(100), i.e. approx. 7 times. Same way, for 1000 elements, it should be 10 times.
3. O(n) - Linear Time: The most common complexity and usually consider as good performance. Here the complexity is equal to the size of the inputs.
For example,
for i in 1...10{
print(i)
}
The above FOR loop will be running 10 times as it should traverse through 10 elements. So the complexity of this loop is O(10). Same way, traversing an Array or Adding element in a specific index or linear search on an Array are having complexity O(n), where n is the total number of Array elements.
4. O(n log n) - Linearithmic Time: Slightly worse than the linear, but it’s still acceptable. Any divide-and-conquer approach which divides a big problem into small pieces of the problem and then solves is having the complexity of O(n log n) where n is the total inputs.
For example,
func mergeSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array }
let middleIndex = array.count / 2
let leftArray = mergeSort(Array(array[0..<middleIndex]))
let rightArray = mergeSort(Array(array[middleIndex..<array.count]))
return merge(leftPile: leftArray, rightPile: rightArray)
}
The above example of merge sort in Swift, where we can sort elements of an Array by, first decided into two parts, then sort each of the parts and lastly merge all the part together to have sorted Array. Same way, Heap sort or quick sort are having the complexity of O(n log n).
5. O(n^2) - Quadratic Time: Comparably slow in performance. The complexity of this algorithm square up the total number of inputs. If the input size is 10, the complexity of this algorithm would be 10*10 or 10^2 or 100.
For example,
var twoDimensionalArray: [[Int]] = [[0, 1], [2, 3]]
for i in 0..<twoDimensionalArray.count {
for n in 0..<twoDimensionalArray[i].count {
print(twoDimensionalArray[i][n])
}
}
Above is an example of traversing a 2D Array. As it contains two nested loops, it’s doubled up the iterations. Similar way, Bubble sort or Insertion sort or Selection sort are having the complexity of O(n^2) where n is the total number of elements.
Depending on the number of nested loops, this complexity will increase exponentially. For example, if you want to do matrix multiplication, you should have 3 nested loops and then the complexity would be O(n^3). Same way, for 5 nested loops having the complexity of O(n^5), and so on.
6. O(2^n) - Exponential Time: Poor in performance, recommended avoiding these kinds of algorithms. Algorithms with the complexity of O(2^n) are often recursive algorithms that solve a problem of size n by recursively solving two smaller problems of size n-1.
func solveHanoi(n: Int, from: String, to: String, spare: String) {
guard n >= 1 else { return }
if n > 1 {
solveHanoi(n: n - 1, from: from, to: spare, spare: to)
solveHanoi(n: n - 1, from: spare, to: to, spare: from)
}
}
The above Swift code will print, the necessary steps to solve the famous "Towers of Hanoi" problem for n disks. Depending on the number of disks, here is n, the complexity will increase exponentially to O(2^n) times. Fibonacci Series may be another example.
7. O(n!) - Factorial Time: The slowest one in performance and recommended to always ignore such an algorithm. The complexity will increase abnormally based on the number of inputs, as it takes the factorial value of input numbers. An infinite loop will be the best example of this scenario.
Usually, you don't need typical mathematical calculations to figure out what the Big-O of an algorithm is but you can simply use your intuition. If your code uses a single loop that looks at all n elements of your input, the algorithm is O(n). If the code has two nested loops, it is O(n^2). Three nested loops give O(n^3), and so on.
Remember, Big-O notation gives an estimated value and is only really useful for large values of n. For example, the worst-case running time for the insertion sort algorithm is O(n^2). In theory that is worse than the running time for merge sort, which is O(n log n). But for small amounts of data, insertion sort is actually faster, especially if the array is partially sorted already. So here, the developer’s experience works to find out a better algorithm.
The following graph will give you a better idea on an algorithm’s performance with “Big O notation”.
Problem statement
Say, we have a requirement for sort a number Array. The Array may look like this,
let list = [ 10, 1, 31, 9, 21, 27, 8, 50, 15, 35]
Developers may pick any kind of sort algorithm available in the Data Structure concept. Assume, a developer picks the Selection Sort Algorithm for this job. The Selection Sort in Swift may look like this.
func selectionSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array }
var a = array
for x in 0 ..< a.count - 1 {
var lowest = x
for y in x + 1 ..< a.count {
if a[y] < a[lowest] {
lowest = y
}
}
if x != lowest {
a.swapAt(x, lowest)
}
}
return a
}
selectionSort(list) // O(n^2)
If we closely observe the flow pattern of this Selection Sort, we will find that,
First, It found the lowest element from the entire Array called list and placed it at the beginning of the Array. From the second element onwards, it will search for again lowest element and then place it to the second position of the Array. Step 2, continues until the end of the Array element. So, for Selection Sort, the Best-Case Complexity is О(n^2) and Worst-Case Complexity is О(n^2). That means the Selection Sort is slow in performance.
Solutions
You can pick the best algorithm for sort among Heap or Quick Sort. In this example, let’s look into Quick Sort to get better performance than above Selection Sort.If we need to rewrite the sort algorithm for Quick Sort, it may look like,
func quicksort<T: Comparable>(_ a: [T]) -> [T] {
guard a.count > 1 else { return a }
let pivot = a[a.count/2]
let less = a.filter { $0 < pivot }
let equal = a.filter { $0 == pivot }
let greater = a.filter { $0 > pivot }
return quicksort(less) + equal + quicksort(greater)
}
quicksort(list) // O(n log n)
The above algorithm works on the divide-and-conquer approach. We used generic type Comparable for this quicksort() so that we can use Swift functionals like “filter”.
1. Based upon central element or “pivot”, the Array called list, has been sliced into three parts.
a) Any element less than the pivot goes to the less part.
b) Any element greater than the pivot goes to the greater part.
c) Any element equal to the pivot goes to the equal part.
2. These less and greater parts are then recursively sorted.
3. Once these less part and greater part are sorted, will be glued together with equal part to form the complete sorted Array.
So, for Quick Sort, Best-Case Complexity is O(n log n) and Worst-Case Complexity is O(n log n)
Conclusion
Usually, “Big O notation”, tells a developer about an Algorithm that, how fast the runtime grows for arbitrarily large input sizes? And the worst-case scenario for an algorithm. As a developer, you must consider the worst-case scenario to decide whether the Algorithm gives better performance on all scenarios or not.As we saw here, Quick Sort is better than the Bubble or Selection or Insertion Sort. But it doesn’t mean that we should ignore those sorts completely. After all Bubble sort is one of the favorite sort Algorithm among developers.
For example, if you want to search an element from an Array,
- If the element is the 1st element of the Array, the search complexity would be O(1).
- If the element is somewhere in the middle, the search complexity would be O(log n).
- If the element is the last one, the search complexity would be O(n).
#computer #science #programming #swift #bigo #algorithm #sort #quicksort #selectionsort #mergesort #binarysearch #hanoi #twodimentionarray
Comments
Post a Comment