CODEWITHSUNDEEP
algorithmsortingbig-o
Gagan
Gagan

Reputation: 5656

Big(O) notation - which one is correct

I am trying to learn Big(O) notation. While searching for some articles online, I came across two different articles , A and B

Strictly speaking in terms of loops - it seems that they almost have the same kind of flow. For example

[A]'s code is as follows (its done in JS)

function allPairs(arr) {
    var pairs = [];
    for (var i = 0; i < arr.length; i++) {
        for (var j = i + 1; j < arr.length; j++) {
            pairs.push([arr[i], arr[j]]);
        }
    }

    return pairs;
}

[B]'s code is as follows (its done in C)- entire code is here 

  for(int i = 0; i < n-1 ; i++) {
    char min = A[i]; // minimal element seen so far
    int min_pos = i; // memorize its position
    // search for min starting from position i+1
    for(int j = i + 1; j < n; j++) 
      if(A[j] < min) {
        min = A[j];
        min_pos = j;
      }
    // swap elements at positions i and min_pos
    A[min_pos] = A[i];
    A[i] = min;
  }

The article on site A mentions that time complexity is O(n^2) while the article on site B mentions that its O(1/2·n2).

Which one is right?

Thanks

Upvotes: 1

Views: 83

Answers (2)

user1196549
user1196549

Reputation:

You didn't read carefully. Article B says that the algorithm performs about N²/2 comparisons and goes on to explain that this is O(N²).

Upvotes: 2

Lorelorelore
Lorelorelore

Reputation: 3393

Assuming that O(1/2·n2) means O(1/2·n^2), the two time complexity are equal. Remember that Big(O) notation does not care about constants, so both algorithms are O(n^2).

Upvotes: 3

Related Questions