Is this function O(n) or O(log(n)) time complexity.
function reverse(array) {
for (var i = 0, j = array.length - 1; i < j; i++, j--) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}
At first glance it appears to be making n/2 iterations over the input. However, if you think about it, the actual number of lower level operations is closer to 2n.
So assume you have a string of length n
Then you have indicators i=0
, and j = n-1
The loop continues until i>=j
with j
decrements by 1 and i
increments by 1
This will give you a total of n/2
iterations.
Inside the loop you have a total 3 statements meaning the loop will complete a total of 3(n/2)
. Along with that you have 1 operation outside the loop leaving us with
f(n) = 3(n/2)+1 which is O(n)
EDIT: This assumes that the loop maintaining operations(i++
,j--
) are trivial which is common practice when dealing with Big Oh notation
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