DEV Community

Jose Ross Barredo
Jose Ross Barredo

Posted on

1 1

Question: How was the assumption made?

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 N^2 total pairs. Roughly half of those will have i < j and the remaining half will have i > j. This code goes through roughly n^2/2 pairs so it does O(N^2) 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!

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay