Why is the complexity of reverse algorithm O(n)?

Question

I have this implementation of reverse algorithm:

function reverse(a) {
    let left = 0;
    let right = a.length - 1;

    while (left < right) {
        let tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;

        left += 1;
        right -= 1;
    }

    return a;
}

For any array of n elements the loop will run n/2 times. But I read everywhere that reverse algorithm complexity is O(n)? So why is the complexity O(n)? Because of two operations on each cycle?

Looks like a question for https://cs.stackexchange.com/help/on-topic — mplungjan, Apr 19 '17 at 17:40
Big O notation is not affected by constant multipliers - so whether you have `n/2` operations `1000*n` operations, both will simply be `O(n)` — Wrokar, Apr 19 '17 at 17:41
It I really important for you? Just use exists Array.prototype.reverse and show your users cats in internet. — , Apr 19 '17 at 17:42

score 0 · Answer 1 · answered Apr 19 '17 at 17:42

0

The Big-O of an algorithm refers to the time complexity of the algorithm in terms of n. Since the reverse method increases linearly with n, it is said to be O(n) even though the number of swaps may c*n (with c constant)

answered Apr 19 '17 at 17:42

Matias Szylkowski

1
2

score -1 · Answer 2 · answered Apr 19 '17 at 17:42

-1

o(n) means a function of n or some multipler of n ( not any other power of n) . n/2 a function of n (not n power -1 or n power2) hence its o(n). p.s.-this is based on the question of o(n) without even going to the logic of the code

answered Apr 19 '17 at 17:42

Bhabani Das

380
5
13

There is no shift button on your keyboard? It is called Big-O for a reason.... Also this definition of *O(n)* is not correct. `e^x` is also *"a function of n"*, but is not *O(n)*. – trincot Apr 19 '17 at 17:43
I thought that was something else. Something after manipulating G – mplungjan Apr 19 '17 at 17:47
I get what you're trying to say with "a function of n", but e.g. n^2 is a function of n, so that's just confusing / misleading. – Bernhard Barker Apr 19 '17 at 17:52

Why is the complexity of reverse algorithm O(n)?

2 Answers2