“Introduction to Algorithms” Exercise 1.2-2

I’ve just started reading “Introduction to Algorithms,” Third Edition, by Cormen, Leiserson, Rivest, and Stein as part of my self-designed, self-taught course in making me a better software developer. I’m two sections in to the first chapter, and what I’m realizing I’m going to need to study up on some fairly elementary algebra. But, I stumbled my way through a problem with base 2 logarithms in play. Here’s my victory for today.

The question was this:

1.2-2  Suppose we are computing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n² steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort?

So, I set up the equation:

8n² < 64n lg n

Divide by 8, and we get:

n2 < 8n lg n
Or: (n)(n) < 8n lg n

So, divide both sides by n and get:

n < 8 lg n

If we then divide both sides by 8, we end up with:

n/8 = lg n

Now, multiply both sides by 1/n, and we get:

1/8 = lg n / n

Beyond that point, I just pulled out my calculator and started inserting numbers for n and figuring out whether or not the statement was true, as follows:

n = 10:      .1250 < .3322 = TRUE
n = 1:         .1250 < 0 = FALSE
n = 2:         .1250 < 5 = TRUE
n = 20:      .1250 < .2161 = TRUE
n = 30:      .1250 < .1636 = TRUE
n = 40:      .1250 < .1774 = TRUE
n = 50:      .1250 < .1129 = FALSE
n = 45:      .1250 < .1220 = FALSE
n = 44:      .1250 < .1241 = FALSE
n = 43:      .1250 < .1262 = TRUE

So, for integer values (since we can only sort whole numbers of items):

2 <= n <= 43

Now, I’ve only got a natural logarithms button on my Texas Instruments BAII Plus calculator (at least, I’m only AWARE of natural logarithms button on that calculator), so I had to search the web to figure out that to get Log₂(x) I could divide Ln(x) by Ln(2) (thanks to TVMCalcs.com for that assist!).

If anyone could remind me of a better way to figure out the range of acceptable answers here than the “guess and check” with the calculator, please leave a comment.  Such would be greatly appreciated!  But, I’m glad I was at least able to come up with an answer this way, and wanted to post about it.

Checking on the Children: Which loop to execute?

I’ve been reading Advanced Apex Programming for Salesforce.com(R) and Force.com(R) by Dan Appleman.  If you’re an Apex programmer, or are aspiring to be one, I highly recommend buying a copy.  I’ve already learned a lot from it, and I’m only in Chapter 4 of 11.

On pages 80 – 82, Appleman introduces a concept that I decided to look at with some code of my own.  He says, “One question that you’ll often face is choosing which object to loop through.”  In this case, Appleman was talking about a method to find Opportunity records without child Task records.  I decided to use custom objects and write a method to check for child objects to make sure I understood his concept.  I went with a concept familiar to me from work on systems I deal with daily: Invoices and Invoice Line Items.

PLEASE NOTE:   The following code is based on Appleman’s samples in Chapter 4 of Advanced Apex Programming…, though mine is far less elegant, and uses custom objects instead of CRM standard objects.

public with sharing class InvoiceIdeas {

 public static Set<Invoice__c> findInvoicesWithNoLineItems(List<Invoice__c> invoicesToCheck) {
 
 Map<Id, Invoice__c> invoiceMap = new Map<Id, Invoice__c>(invoicesToCheck);
 
 Set<Id> invoiceIds = new Set<Id>();
 for(Invoice__c i : invoicesToCheck) {
 System.debug('AN INVOICE ID ADDED...');
 invoiceIds.add(i.Id);
 }
 
 // In terms of worst-case analyis for bulkification, let's say an invoice might have as 
 // many as 30 line items, time 200 possible invoices passed in, for 6000 total records.
 List<Invoice_Line_Item__c> allInvoiceLineItems = [ SELECT Name, Invoice__c FROM Invoice_Line_Item__c
 WHERE Invoice__c = :invoiceIds ];
 
 Set<Invoice__c> invoicesWithoutLineItems = new Set<Invoice__c>();
 for(Invoice__c i : invoicesToCheck) {
 invoicesWithoutLineItems.add(i);
 }
 
 Integer loopIterations = 0;
 
 // Option 1: Loop through all the Invoice records, and see if they have any line items.
 /*
 for(Invoice__c inv : invoicesToCheck) {
 for(Invoice_Line_Item__c lineItem : allInvoiceLineItems) {
 if(inv.Id == lineItem.Invoice__c) invoicesWithoutLineItems.remove(inv);
 loopIterations++;
 }
 }
 */
 
 // Option 2: Loop through the Invoice_Line_Item__c list, and remove their parent Invoice__c
 // record's ID from the set invoicesWithoutLineItems.
 
 for(Invoice_Line_Item__c lineItem : allInvoiceLineItems) {
 Invoice__c inv = invoiceMap.get(lineItem.Invoice__c);
 invoicesWithoutLineItems.remove(inv);
 loopIterations++;
 }
 
 
 System.debug('NUMBER OF LOOP ITERATIONS: ' + loopIterations);
 for(Invoice__c i : invoicesWithoutLineItems) {
 System.debug('Invoice without line item: ' + i.Id);
 }
 
 return invoicesWithoutLineItems;
 
 }

}

I then created 3 invoices in my developer org; one with no line items, and two more with three line items each.

Next, I went into the Execute Anonymous window in the Force.com IDE plugin for Eclipse and ran the following:

List<Invoice__c> myInvList = [ SELECT Id, Name FROM Invoice__c ];

InvoiceIdeas.findInvoicesWithNoLineItems(myInvList);

When I use “Option 1” above, I get 18 iterations of the inner loop. When I use “Option 2” above, I get only 6 iterations of the single loop. So, back in the day when Salesforce was limiting our number of script statements, I can see how our choice of which object to loop through was extremely important. These days, the governor limit we, as developers, have to worry about around this and similar patterns is the CPU time limit. In this case, I put a call to this method (with the Option 1 code running) in a for loop that ran 50 times, and I still didn’t get anything but 0 registering as the CPU time. However, it stands to reason that in a different context with more work being done in the loop(s), this pattern would save us a significant amount of CPU time.