0

I'm sure this must be a typical example but I'm very new to calculating O notations from an algorithm. Ideally, the answer to this question wouldn't just give the big-O notation but explain how to find it from looking at the algorithm.

// Apply Newton's law of universal gravitation
    for (let n = 0; n < sky.length; n++) {
        let celestial = sky[n]

        for (let m = n + 1; m < sky.length; m++) {
            let melancholia = sky[m]

            let gravity = // Code to calculate gravity

            // Apply gravity to celestial
            celestial.applyGravity(gravity)

            // Apply reversed gravity to melancholia
            gravity.mult(-1)
            melancholia.applyGravity(gravity
        }

        celestial.update()
    }

I optimized the code from O(n^2) with let m = n + 1 instead of let m = 0. Now, I recorded O values for certain n values and got a graph looking like: Graph of O values for certain n values

Hugo
  • 349
  • 3
  • 6
  • 23
  • "I optimized the code from O(n^2)"--what complexity do you think you optimized it to? – ggorlen Jan 14 '20 at 16:19
  • @ggorlen If I know the answer to that question I wouldn't be asking this question. it still looks exponential to me, but not as much obviously. – Hugo Jan 14 '20 at 16:21
  • 2
    You might want to check out a basic tutorial on big O. Exponential is O(2^n), which is worse than quadratic. This code is still O(n^2) after the optimization assuming all the operations are O(1). Big O describes the growth rate relative to `n`, which is unchanged--it's still a quadratic curve. – ggorlen Jan 14 '20 at 16:23
  • 1
    What are the timing complexity for celestial.applyGravity(gravity) and melancholia.applyGravity(gravity). If these two are O(1) then the overall complexity will be O(n^2) – User_67128 Jan 14 '20 at 16:25
  • 1
    Indeed, it's still O(n²), but note that it's twice as fast now. It's just that the constant factors are irrelevant in the big-O notation, so this is not noticed. – Ruslan Jan 14 '20 at 16:26
  • If you drew a graph from your measures, then add common polynomial on your graph and you will be able to see n^2, 2^n, n and adjust some multiplicative factors... You will have a good hint. – Jean-Baptiste Yunès Jan 14 '20 at 16:28
  • Okay, so because this is still an exponential it stays O(n^2) even though it's faster. Alright, that's simpler than I expected. Thanks! – Hugo Jan 14 '20 at 16:32
  • @Jean-BaptisteYunès I have no idea what adding common polynomial or adjusting some multiplicative factors means – Hugo Jan 14 '20 at 16:33
  • 1
    It means not only draw your measures but values of n^2, n^3, or n^2/2 or things like that... Thus you will be able to compare the curves... – Jean-Baptiste Yunès Jan 14 '20 at 16:47
  • Oh! @Jean-BaptisteYunès That's exactly what I was missing thank you – Hugo Jan 14 '20 at 16:53

1 Answers1

0

Let us suppose that inner calls to applyGravity and alike are constant time. You already know that:

for (let n = 0; n < N; n++) {
    for (let m = 0; m < N; m++) {

is O(n^2) because the outer loops N times and for each value the inner loops N times, thus N*N.

Now you have:

for (let n = 0; n < N; n++) {
    for (let m = n; m < N; m++) {

the outer loops again N times, but now for each value n the inner loops N-n times. Let look at the generated pairs (n,m):

When N=1, you'll have (0,0)

When N=2, you'll have (0,0), (0,1), (1,1)

When N=3, you'll have (0,0), (0,1), (0,2), (1,1), (1,2), (2,2)

When N=4, let us draw it this way:

(0,0) (0,1) (0,2) (0,3)
      (1,1) (1,2) (1,3)
            (2,2) (2,3)
                  (3,3)

Don't you see that it will always draw half a square? So something like N^2/2 (surface of a square is N^2), thus in big-O it will be O(n^2), because you can forget any multiplicative constant: N^2 and 1345456*N^2 behave the exactly same.

Exact complexity is N+(N-1)+....+1, which is well known to equals to N(N+1)/2 = (N^2+N+1)/2.

It has the same big-O complexity but not the same exact complexity, that means both behave almost the same as N grows but one can run faster than the other. Remark that as one comment says: the second algorithm executes almost twice as fast as the first one (because (N(N+1)/2) / (N-2)) rouhgly equals to 1/2 as N grows).

Jean-Baptiste Yunès
  • 34,548
  • 4
  • 48
  • 69