Menu
I am trying to compare the contents of two disparate file systems. My current solution is to create two lists. One for each file system. The items on this list are multi-dimensional and summarize the unique qualities of the file itself — like a primary key. Since the list are constructed using the same algorithm for each file system, the items on the list should match if the files match.
Does this seem logical?
Depending on what I am doing, I may end up iterating over the lists a large number of times and I am concerned about performance, but my computational theory is rusty.
Let say the list is an indexed array of associative arrays, and let’s call the lists A and B. To compare each, it would be great to just pick an item from A and see if it matches one on B… which would be an O(n) algorithm.
Now, since the items on the list are multidimensional, it’s impossible to directly make this comparison. We have to look at each sub-item (the associative array) of the items on the A list, and compare it to each sub-item on each item of the B list. Does this mean it becomes O(n^2)? Sub-items never have more than 5 or so elements, so would this perhaps become a lower order term and not even be considered? Or, perhaps it makes it O(5n) or something?
Sorry for the long setup, but I think you can see where I am going with this. What Big O notation would this algorithm receive? Keeping in mind that each item must find its match, so each item (and all 5 sub-items) from A are compared to B, much like you’d find a list of words in the dictionary where A is the list, and B is the dictionary.
Is there a more optimal way? Perhaps sorting first or something?
Thanks for any responses,
Tyler