# Question: suppose you have an array of length 2n consisting of...

###### Question details

Suppose you have an array of length 2N consisting of N B's followed by N A's. Below is the array for N=10:

B B B B B B B B B B A A A A A A A A A A

How many compares will Insertion Sort take as a function of N? (constant, n^2, n^3, etc)

Could the array below exist during execution of the Weighted Quick Union algorithm??

0 1 2 3 4 5 6 7 8 9

----------------------------

a[i] 3 3 6 9 3 6 3 4 1 9