Find complexity of algorithm using step count

Question

First of all - yes, I have read several posts here on SO, as well as other places about estimating the complexity of an algorithm.

I have read this, this and this, as well as others

I want to try with an algorithm I wrote that finds the largest rectangle, to see if I understood anything at all from what I've read.

public static long getLargestRectangle(long[] arr, int index, long max) {
    int count = 1;      //1 step * 1                               
    int i = index - 1;   //1 step * 1
    int j = index + 1;  //1 step * 1

    if(index == arr.length-1) return max; //1 step * 2

    while(i > -1 && arr[index] <= arr[i]) { //1 step * (N+1)
        count++;                             //1 step * N
        i--;                                 //1 step * N
    }
    while(j <= arr.length-1 && arr[index] <= arr[j]) { //1 step * (N+1)
        count++;                                        //1 step * N
        j++;                                            //1 step * N
    }

    max = (max < (arr[index] * count) ? (arr[index] * count) : max); //1 step * 7

    return getLargestRectangle(arr, index + 1, max); //1 step * 1
}

    //total number of steps: 1 + 1 + 1 + (N + 1) + N + N + (N + 1) + N + N + 7 
    //=> 6N + 12 = O(N) ?

Am I way off here? I'd love some insight.

EDIT

Like this?

T(n) = O(N) + T(n+1)
T(n) = O(N) + O(N) + T(n+2)
T(n) = O(N) + O(N) + O(N) + T(n+3)
T(n) = i * O(N) + (n+i)
T(n) = n * O(N) + (n+n)
= O(N^2)

If this is wrong, I'd really appreciate if you could update your answer and show me.

Where are the rectangles? It seems like you are only comparing longs — ControlAltDel, Jun 03 '15 at 19:51
@ControlAltDel in the array I store different heights and calculate what the the largest rectangle that can be produced based on those heights is. — Nilzone-, Jun 03 '15 at 19:53
This is a very famous problem going by the name "Largest Rectangular Area in a Histogram." I would recommend googling it if you're having trouble grasping how to solve it or to see explanations of the complexity of common approaches. It can be solved efficiently in O(n). — Synergist, Jun 03 '15 at 20:05
You should also learn how to do rudimentary complexity tests. Just time the algorithm for varying array input sizes, and plot your results. You would quickly see that your approach is not linear in complexity. — Synergist, Jun 03 '15 at 20:07
@Synergist My code takes 0,69 seconds when there is 100.000 elements. — Nilzone-, Jun 03 '15 at 20:09
@Nilzone- **varying** input sizes. test it for 10, 100, 1000, 10000 elements — Synergist, Jun 03 '15 at 20:10

score 2 · Answer 1 · answered Jun 03 '15 at 19:51

Am I way off here? I'd love some insight.

I am afraid so :(

return getLargestRectangle(arr, index + 1, max); //1 step * 1

This above is NOT 1 step, it is a recursive invokation of the method. This method "shrinks" the array by 1 element, so this step actually costs T(n-1), where T(.) is the time complexity of the algorithm.
Combining this with what you already have, you get

T(n) = T(n-1) + O(N)

Solving this recurrence formula will give you the algorithm's complexity.

Note: T(n) = T(n-1) + O(N) is a syntatic sugar, it should actually have been T(n) <= T(n-1) + CONST*N for some constant CONST, since you cannot add a set (O(N)) to a scalar (T(n-1)).

Also note: N!=n. n changes over time, N is the initial length of the array. It is so because your algorithm is actually traversing from n (index) to 0, and from n to N.
This does not change the time complexity in terms of big O notation, however.

Find complexity of algorithm using step count

1 Answers1