Decrease big-O for nltt_diff_exact_norm_brts

[richelbilderbeek]

The function nltt_diff_exact_norm_brts may have O(n^2) complexity, as:

• O(n): a for loop over the branching times
• O(n): max of the branching times

  for (k in 2:length(all_b_times)) {
      tim <- all_b_times[k]
      #find the index of the first branching time
      #that is up to the focal branching time
      index1 <- max(which(b_times_N < tim))
      index2 <- max(which(b_times2_N < tim))  #same for the other tree
      # ...
  }

Options to explore are:

• Use an implementation of finding the upper bound for sorted data, O(log n)
• Let index1 and index2 increase manually

TODO:

• [ ] Create a test to check for valid results
• [ ] Create nltt_diff_exact_norm_brts_impl_1 that has the current behavior
• [ ] Create nltt_diff_exact_norm_brts_impl_2 that has the new behavior
• [ ] Create a test to check that the new implementation is faster for bigger data

[richelbilderbeek]

Lost interest, closing Issue for now.