Time Complexity in Swift

Data structures & Algorithm | Interview Topic

Time complexity of an algorithm quantifies the amount of time required to run an algorithm as the input increases. Big O Notation is used to express the time complexity of an algorithm.

As mentioned in the geeksforgeeks.org,

Instead of measuring the actual time required to execute a statement in the code, Time Complexity considers how many times a statement executes.

https://www.geeksforgeeks.org/understanding-time-complexity-simple-examples

Different Complexity Classes

Constant Time — O(1)

Constant running time regardless of input data size.

Let’s consider the following code.

No matter how many items are in the input array, the execution time remains constant because the above function only checks for the first item.

Linear Time — O(n)

The running time increases linearly as the input size increases.

Let’s consider the following code.

The number of iterations for the for loop increases linearly as the input names array size increases. Here, the time is dependent on the data size.

Quadratic Time — O(n²)

The running time increases drastically to the square of the input size. Also referred to as n squared.

Let’s consider the following code.

For an input size of 10, this print function will execute 10x10 times. So, the time complexity for the above function is proportional to the square of its input size.

Logarithmic Time — O(log n)

The running time increases at a very slow rate as the input data size increases.

Let’s consider the following code.

In all repeating divide-and-conquer algorithms, such as merge sort & binary search, logarithmic time is efficient. In the above binary search function, at each iteration, it compares the middle element of the array with the search element to determine the correct half, and it reduces the number of executions by half.

Quasilinear Time — O(n log n)

Despite a small amount of data, the running time increases, but as the size of the data increases time balances out. It performs better than quadratic time but worse than linear time. Swift’s sort method is an example of Quasilinear time complexity. Its big O notation is the multiplication of linear and logarithmic time — O(n log n).

Thanks for Reading! ✌️

Hope you find this article helpful🥳. If you have any questions or corrections, please leave a comment below.