Skip to content
loading...

Question: How was the assumption made?

twitter logo github logo ・1 min read  

Hi guys! I have been reading "Cracking the Coding Interview 6th Edition".. On Chapter 0 - Big O, I have problem understanding an assumption made to a problem on Example 3.

void printUnorderedPairs(int[] array){
  for(int i = 0; i < array.length; i++){
    for(int j = i + 1; j < array.length; j++){
      ...
    }
  }
}

Under What It Means section, it assumed that:

There are N2 total pairs. Roughly half of those will have i < j and the remaining half will have i > j. This code goes through roughly n2/2 pairs so it does O(N2) work.

My question is, how was the assumption made on Roughly half of those will have i < j and the remaining half will have i > j done? Can someone explain it to me please?

Thanks!

twitter logo DISCUSS
Classic DEV Post from Aug 14 '19

What Does Your IDE/Code Editor Look Like?

Jose Ross Barredo profile image
25. Coder. Noob. INTP-T