Menu
I'm working through some practice problems where I'm given a target time complexity and space complexity. One of them gives a target time complexity of O(N+M). I'm having some trouble with the intuition of what an O(N+M) algorithm would look like. Does anyone have an example of an algorithm like this or can explain it clearly? Every example I try to think of seems like O(N*M) to me.
410
To sum up: O(mn) is generally called linear for things like matrix multiplication because it's linear in the size of the input, but it's generally called quadratic for things like string matching because of the smaller input.
For the input of size n , an algorithm of O(n) will perform steps perportional to n , while another algorithm of O(log(n)) will perform steps roughly log(n) . Clearly log(n) is smaller than n hence algorithm of complexity O(log(n)) is better. Since it will be much faster.
The algorithm will just iterate through the array once, which results a time complexity of O(n). Therefore, we would say that the best-case time complexity of insertion sort is O(n). A complexity of O(n) is also often called linear complexity.
O(nlogn) is known as loglinear complexity. O(nlogn) implies that logn operations will occur n times. O(nlogn) time is common in recursive sorting algorithms, sorting algorithms using a binary tree sort and most other types of sorts. The above quicksort algorithm runs in O(nlogn) time despite using O(logn) space.
A simple example of algorithm that is O(m+n):
int sum(int[] nArr, int[] mArr) { int sum = 0; for(int i : nArr) { sum += i; } for(int i : mArr) { sum += i; } return sum; } To compute the sum, you need to go through all elements in nArr (size n) and all elements in mArr (size m), so the overall complexity is O(m+n)
113
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
