14
int j=0;
for (int i=0; i<N; i++) 
{
    while ( (j<N-1) && (A[i]-A[j] > D) )
        j++;
    if (A[i]-A[j] == D) 
        return 1; 
}

This code is said to have the time complexity of O(n), but I don't really get it. The inner loop is executed N times and the outer should be also N times? Is it maybe because of the j = 0; outside the loop that is making it only run N times?

But even if it would only run N times in the inner loop, the if statment check should be done also N times, which should bring the total time complexity to O(n^2)?

Some programmer dude
  • 400,186
  • 35
  • 402
  • 621
lomo133
  • 158
  • 9
  • 7
    Look at it this way: j++ won't be executed more than N-1 times. It's not set to 0 at each outer loop iteration start. – algrid Dec 13 '18 at 21:38
  • 1
    The inner loop is not *repeatedly* executed `N` times. That will only happen *once*. Once `(j – WhozCraig Dec 13 '18 at 21:42
  • 1
    Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – cirrusio Dec 13 '18 at 21:44

1 Answers1

15

The reason why this is O(n) is because j is not set back to 0 in the body of the for loop.

Indeed if we take a look at the body of the for loop, we see:

while ( (j<N-1) && (A[i]-A[j] > D) )
    j++;

That thus means that j++ is done at most n-1 times, since if j succeeds N-1 times, then the first constraint fails.

If we take a look at the entire for loop, we see:

int j=0;
for (int i=0; i<N; i++) {
    while ( (j<N-1) && (A[i]-A[j] > D) )
        j++;
    if (A[i]-A[j] == D) 
        return 1;
}

It is clear that the body of the for loop is repeated n times, since we set i to i=0, and stop when i >= N, and each iteration we increment i.

Now depending on the values in A we will or will not increment j (multiple times) in the body of the for loop. But regardless how many times it is done in a single iteration, at the end of the for loop, j++ is done at most n times, for the reason we mentioned above.

The condition in the while loop is executed O(n) (well at most 2×n-1 times to be precise) times as well: it is executed once each time we enter the body of the for loop, and each time after we execute a j++ command, but since both are O(n), this is done at most O(n+n) thus O(n) times.

The if condition in the for loop executed n times: once per iteration of the for loop, so again O(n).

So this indeed means that all "basic instructions" (j++, i = 0, j = 0, j < N-1, etc.) are all done either a constant number of times O(1), or a linear number of times O(n), hence the algorithm is O(n).

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • There's something a bit strange about your choice of notation. A loop does not "execute O(n) times." – Robert Harvey Dec 13 '18 at 21:41
  • @RobertHarvey: well the number of iterations scales *O(n)*, is that better wording? – Willem Van Onsem Dec 13 '18 at 21:44
  • A loop is said to *"have O(n) time complexity."* See https://en.wikipedia.org/wiki/Time_complexity. Big O notation *"describes the limiting behavior of a function as n approaches infinity."* See https://en.wikipedia.org/wiki/Big_O_notation – Robert Harvey Dec 13 '18 at 21:45
  • @RobertHarvey: but here I'm not really talking about the *time* complexity of the *loop* itself (yes eventually that is what we conclude), here we say that the number of loops scales *O(n)*, just like memory can also scale *O(n^2)* for example. After all *O(f(n))* produces a set of functions, and one of the functions describes the exact number of iterations of the loop. – Willem Van Onsem Dec 13 '18 at 21:47
  • Just say "the body of the for loop is executed `n` times." – Robert Harvey Dec 13 '18 at 21:48
  • @RobertHarvey: I still do not really see what is the problem with saying that the number of iterations scales O(n), I also read similar parts often in books like *Computational complexity, a modern Approach*, for example says things like "*we can repeat this procedure O(1/d) times*", or "*by testing Condition (4) repeatedly O(k) times*". Based on a study group I was a member of in academia, big oh, deals with the asymptotic behavior of a function, but that does not per se is the amount of time it takes to calculate a function, it can also deal with other measurements like counts, memory, etc. – Willem Van Onsem Dec 13 '18 at 22:08
  • It's just the first time I've ever seen this form of usage, that's all. Normally I'm not a nazi about things like this, but lately I've seen far too many people make up arbitrary terminology and declare it "official" or "common" usage. And yes, that includes book writers. That the phrase "The loop executes n times" is the correct way to write it seems self-evident to me. – Robert Harvey Dec 13 '18 at 22:11
  • And your last edit further strengthens my assertion. You can't credibly say "The loop executes at most O(2×n-1) times," because there is no such thing as O(2×n-1). – Robert Harvey Dec 13 '18 at 22:16
  • @RobertHarvey: But here I'm not writing *O(2n-1)* but just *at most 2n-1*, and furthermore in fact there is such thing as *O(2n-1)*, it is however simply equal to *O(n)*. After all *O(..)` is just a function that maps a given function to an (infinite) set of functions, as described [here](https://cs.stackexchange.com/questions/101324/o-is-not-a-function-so-how-can-a-function-be-equal-to-it/101335#101335) – Willem Van Onsem Dec 13 '18 at 22:20
  • We can unfortunately not say that the condition is done *n* times, or *2n* times (or another derivative), since the strict number really depends (partly) on the values stored in *A*, if the *A* is a list that contains one *unique* value (and `D` is larger than `0`), then the condition is checked *n* times, but if *A* is shaped differently, then it can go up to *2n-1* checks. – Willem Van Onsem Dec 13 '18 at 22:23
  • 1
    No, but you can still say "at most n times." Suffice it to say that I've been saying "the loop executes n times" my whole career, and I don't see any compelling reason to complicate that simple phrase. – Robert Harvey Dec 13 '18 at 22:24
  • @RobertHarvey: well some papers I've read (at least if my memory is not really failing) use such things, to make reasoning about time complexity *cleaner*. It makes sure that if it is one more, or less this does not results in a discussion. For example the Computational compexlty book mentions things like "*The grid (...) is not a combinatorial expander as a k×k square in the grid has only O(k) neighbors outside it*", whereas the exact number is *4k* neighbors, etc. I actually also found this (initially) a bit "academic lazyness* at first :), but I think I got used to it :s. – Willem Van Onsem Dec 13 '18 at 22:32
  • See for example http://theory.cs.princeton.edu/complexity/book.pdf (here I copied from section 7.5, but well the book contains a lot of parameters that scale with big oh notation). – Willem Van Onsem Dec 13 '18 at 22:33
  • Since `O(k)` doesn't actually describe what the author is attempting to convey, I find that usage rather baffling. Big O describes how an algorithm scales; `O(k)` does not describe the number of neighbors, the number of loop iterations, or the number of anything else; `k` does that. – Robert Harvey Dec 13 '18 at 22:36
  • @RobertHarvey: well I found some other publications (well I did a small search over a digital paper library), without starting to give an exhaustive overview, I found several papers, for example [Thomas Christensen, p75](http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/5335/pdf/imm5335.pdf) "*This means that the loop will have O(n) iterations.*", or Matthias Klush, (A Polynomial Kernel-Oriented Coalition Algorithm for Rational Information Agents) "*In general, each agent is required to perform O(n). communication operation per KCA iteration round, and this is done O(n) times*", etc. – Willem Van Onsem Dec 13 '18 at 22:43
  • You can dredge up all of the examples you want, and it's still for me going to be "Well, most people don't know the real meaning of 'begging the question' because they've used the term wrong for so long that the incorrect meaning has now passed into common usage." No wonder people are constantly confused about Big O. I do like the word "performant" though. :) – Robert Harvey Dec 13 '18 at 22:45
  • A basic grep (well I did not manually went over all hits, I admit) yielded ~500 hits, but that was only for *O(n)*, and probably with some false positives. I've seen such parts typically when the exact number does not really matter in terms of time compexlty, memory complexity, etc. Or when that is simply unknown (so as "preconditions" to the problem, one can say "given this algorithm scales in *O(...), then our "meta-algorithm", will work in O(...)).. – Willem Van Onsem Dec 13 '18 at 22:45
  • But anyway, I've edited the answer in a way that (hopefully) imrpoves readability. – Willem Van Onsem Dec 13 '18 at 22:46
  • 2
    @robertharvey: O(n) describes the asymptotic behaviour of a function. It is orthogonal to the purpose of that function, which is outside the realm of mathematics. Now, if I have a loop in my program, I can certainly say that the loop condition will be true `g(X)` times, where `g(X)` is a function mapping algorithm input `X` to integers. If I can also demonstrate that `g(X)` is in `O(f(|X|))` for some function `f` which maps integers to integers, then I am completely justified in saying the loop executes `O(f(N))` times where `N` is the size of the problem. Why shouldn't I? – rici Dec 13 '18 at 22:54
  • @rici: Why would you go to the trouble of saying all that when you can simply say "The loop executes at most n times"? – Robert Harvey Dec 13 '18 at 22:56
  • @rici: well I think it is a bit "unfortunate" that many computer scientists first see the term when calculating *time complexity*, and "stick with that". Big oh is not really specific to computer science. Another problem I think that definitely makes sense is that `property = O(...)` is syntactically not perfectly sound. It should make more sense to write *property(parameters)&in;O(...)*, since mathematically this describes that after all there is a real function, and that it is a member of the set of functions that *O(...)* returns. – Willem Van Onsem Dec 13 '18 at 22:57
  • @roberyharvey: because maybe I don't know that. Perhaps it executes `n+c` times or `cn` times (where `c` is a constant whose value I don't know). But I can still assert that it executes a number of times which us asymptotically linear in `n`. – rici Dec 13 '18 at 23:00
  • @rici: I'm not disputing any of your rigor. I'm simply stating that if your intent is to convey the idea that a loop executes n times, then that's what you should say. You don't need all of that computer science theory to state that, but that's what you bring to the table when you use the symbol `O(n)` to describe a simple loop. The OP isn't asking for a mathematical treatise; he's asking why his function scales in O(n) and not O(n²). Don't kill a cow to feed your dog when dog food will suffice. – Robert Harvey Dec 13 '18 at 23:03
  • @willem: yes, that was my point about O(n) describing the asymptotic behaviour of a function regardless if what that function will be used for. As for the unfortunate usage of `=`, that point has been driven into the ground and people are still going to use it, in part because of the difficulty of typing the alternative (as seen in your comment). It's also silly that we write sin²Φ instead of (sin Φ)², but we do. Or the wierd notation for differentials. – rici Dec 13 '18 at 23:05
  • 1
    Although I like the discussion, I modified it to more "rigorous" notation. Something that is also noteworthy is that the error of approximative sequences is typically expressed in big oh as well, since here one typically has not enough information at all to specify the exact error (or at least not without exhaustive analysis, that might not be the scope of the paper), as is mentioned in the wiki article. Somehow I forgot about that (been away from academia for too long I guess) https://en.wikipedia.org/wiki/Big_O_notation#Infinitesimal_asymptotics – Willem Van Onsem Dec 13 '18 at 23:09
  • 1
    @Robert: perhaps you disagree but I don't like saying that something happens at most `n` times when it can happen `2n` times. OP asked a question using Big-O notation so responding with Big-O notation is not tossing a completely unfamiliar concept at them. They even identified the issue of counting executions of the test, but got the asymptote wrong. Anyway, we're obviously not going to get any further here right now and I've got a non-CS event to go to. So take care... – rici Dec 13 '18 at 23:13
  • @rici: If it can happen `2n` times, then say that instead. There isn't any usage in this post that requires your specific mental process (as evidenced by the recent edits). – Robert Harvey Dec 13 '18 at 23:15