big O notation exercise

Question

I'm working on an exercise about Big O notations and I was wondering if there are any experts here who could help me determine the notation for the following code. so far, I am assuming that it is O(N^2). because a for loop is called in another loop. What do you guys think?

public static Double average(Integer[] values) {
    Integer sum = 0;
    for (int i = 0; i < values.length; i++) {
        sum += values[i];
    }
    return sum / values.length;
}
public static IDeque < Integer > slidingAvg(
        Stack < Integer > values, int width
) {
    IDeque < Integer > window = new ArrayDeque < > (width);
    IDeque < Double > averages = new ArrayDeque < > (values.size());
    for (int i = 0; i < width; i++) {
        window.pushFirst(0);
    }
    for (int value: values) {
        window.pullLast();
        window.pushFirst(value);
        Integer[] roll = window.toArray(new Integer[0]);
        Double average = average(roll);
        averages.push(average);
    }
    return averages;
}

Although the question is not subjective, your way of writing the question make it seems like it is. — user202729, Feb 06 '18 at 14:46
No it is not. You are processing a window on the `n` values of fixed width so this IMHO is `O(n)`. — OldCurmudgeon, Feb 06 '18 at 14:47
`... because a for loop is called in another loop`. This is a common over-simplification made when considering time complexity; it is not even useful for simple homework problems. It would only be O(N^2) if `values` and `roll` have the same size. — meowgoesthedog, Feb 06 '18 at 14:48
[How to find time complexity of an algorithm](https://stackoverflow.com/q/11032015) — Bernhard Barker, Feb 06 '18 at 15:12
out of curiosity, where does that `IDeque` class/interface come from? — giorgiga, Feb 06 '18 at 18:21
Seems to me that if you want it more efficient, instead of recalculating the next average each time from scratch, you can just update it by multiplying it by the previous size, adding the next number in the sequence, and dividing by size+1 — Gonen I, Feb 06 '18 at 18:27
@giorgiga it's the interface for an array based deque class (linked circular array) except it is made manually with a head and tail pointer assigning values to an array. it's basically the ArrayDeque from the java collection except it's made manually — Henry, Feb 06 '18 at 22:34

score 0 · Answer 1 · answered Feb 06 '18 at 14:49

0

This is O(n).

The algorithm takes n integers and slides a fixed-width window (of size width) of integers across them processing one window per step for n steps.

answered Feb 06 '18 at 14:49

OldCurmudgeon

64,482
16
119
213

1

shoudln't it be `O(n*m)`, because it always processes `m` elements (determined by `width`) over `n` times (number of elements in `values`) – XtremeBaumer Feb 06 '18 at 14:55
@XtremeBaumer - In some circumstances yes but in most interpretations of Big Oh you are looking for how much an increase in the size of the data affects the time cost of the algorithm. In this case I would treat `width` as a constant so the algorithm is `O(n)`. – OldCurmudgeon Feb 06 '18 at 15:09
1

I would never treat a variable as a constant. `width` can change between every call to the method. Lets say the first call is with width = 10 and the second with width = 20. This means a time increase of ~*2. Therefore it shouldn't be constant – XtremeBaumer Feb 06 '18 at 15:16

score 0 · Answer 2 · answered Feb 06 '18 at 18:12

Big O can be derived or calculated, but also can be found programmatically. So with a little extra code right above and below your foreach loop, you can specifically find out what it is. Mark your start and end times, then plug them into a number of items (y) and time(x) graph. For O(1) time should be constant no matter how big your collection is. i.e.. if it takes 10 seconds to loop trough 10 items it will take the same 10 seconds for 1000.

O(N) should show linear proportionality between the total time spent and the collection's size. i.e. if it takes 10 seconds for 10 items, then it will take 1000 seconds for 1000.

In the O(N^2) case, time is exponentially dependent on the number if items. i.e. if it takes 10 seconds for 10 items, then it will take 1,000,000 for 1000.

giorgiga · Accepted Answer · 2018-02-06T22:55:17.537

0

O(N^2). because a for loop is called in another loop

Almost :) Only, the two loops are not executed the same number of times.

Both window.toArray(new Integer[0]) and average(roll) have complexity O(width) and they are each executed values.length times.

The overall complexity is thus O(values.length * width), which can either become O(values.length^2) or O(values.length) depending on how width compares to values.length.

edited Feb 06 '18 at 22:55

answered Feb 06 '18 at 18:43

giorgiga

1,758
12
29

thanks for the help! one thing though >O^2(values.length) or O(values.length) I have not seen these notations so far in my algorithm class. do they mean the same as O(n^2) and O(n) where values.length is the n variable? – Henry Feb 06 '18 at 22:39
@Henry not sure how "canon" it is to use actual variables from the actual code (ie: `values.length` instead of `n`), but I think its clearer than using `n` here since we have the code. Also... OPS! `O^2(values.length)` should be `O(values.length^2)` silly me :) (edited) – giorgiga Feb 06 '18 at 22:55
another thing, big-O considers worst case scenario. wouldn't that mean that the only answer should be O(N^2)? since it's the slowest possible outcome – Henry Feb 07 '18 at 13:08
@Henry Worst case complexity is not the only kind studied, often average time complexity is more interesting (eg: insertion in an array list). Big O is just the name of the maths notation, regardless of where you use it (it is also used in contexts different that CS) – giorgiga Feb 07 '18 at 13:30

big O notation exercise

3 Answers3