CODEWITHSUNDEEP
javaarraysrecursion
user8689296
user8689296

Reputation:

Time complexity of reursion method that reverses array

I was working through a problem where I have to reverse the integers in an array recursively.

public int[] reverse(int[] A, int i){
    if(i = A){
        return;
    }
}

Upvotes: 2

Views: 506

Answers (3)

developer_hatch
developer_hatch

Reputation: 16214

your algo is O(N) because O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set, in your case, besides you divide by 2 the size, if you have an array of n elems, it will take n/2, if you have n+500 elemens, it will takes n+500/2, it means, the /2 is constant, and the algo will grow linearly. Meaning it depends directly of how long is N.

Upvotes: 1

Nir Alfasi
Nir Alfasi

Reputation: 53545

The big O is about scale/magnitude, so O(n/2) == O(n) (read: order of n).

Each time the method is invoked it runs in constant time (because it's doing constant number of actions) so each time the method runs it runs in O(1), BUT we measure the total order of execution of the program, and since calling the method with n > 1 starts a set of recursive calls, we say that the total execution of the program is in order of n => O(n)

Upvotes: 1

Ethan Harlig
Ethan Harlig

Reputation: 766

It is "O(n/2)" but since the multiplication of a constant for big O notation doesn't affect the big O, it is O(n).

Upvotes: 1

Related Questions