If I have n rows in a database, and I want to compare every row against each other, how many loops (or processes) would I need to do.Is it n2? (so if I have 30,000 rows then it would be 900,000,000)Or is it:for (i = 0; i < 30000; i++) {    for (j = i + 1; j < 30000; j++) [         // Process    }}If it is the later, then how many processes is that (and is there an equation to work it out, given n)?Also if I have to process each row y times, how does that affect the calculations?I need to check a database of companies for possible duplicates. To check, they want to do a similarity check on common fields like business name, phone number, etc. If a field difference is under a certain percentage threshold, then mark it as a possible duplicate. I can code this fine by my self, but I am curious about he performance ramifications.
Process each row against each other, how much would it cost?
database;algorithms;complexity
It's O(n2) by definition.The distinction between n2 and your n*(n-1)/2 algorithm doesn't matter.You need to work out a far, far better algorithm for locating duplicates.  This similarity check business is probably the kind of thing that requires a much smarter algorithm than a SQL query.You need to read about fuzzy hashing and metaphone and related techniques.  You need to very clearly define similar and finding a way to detect similar. Doing billions of database operations will take days of run-time. A good rule of thumb is that your RDBMS can fetch about 5000 rows per second.That's 180,000 seconds (50 hours) to do one of these O(n2) queries.A few attributes (let's say a dozen) from 30,000 rows is 360,000 objects. That fits in  memory in any computer larger than iPhone.Here's your algorithm.Read all 30,000 rows into memory.Compute hashes or summaries or whatevers for your dozen or so fields,creating hashmaps or treemaps or whatever makes sense.for x in object_list:    name_map[soundex(x.name)].append(x)    other_map[transformatioN(x.other)].append(x)Write statistical summary reports to be sure your similarity measurements make some kind of rational sense.print( len(name_map), similar names out of, len(object_list) )When you have results you like, update the database with the results.for n in name_map:    similar_set = [ s.primary_key for s in name_map[n] ]    c.execute( UPDATE SOMETHING SET NAME_KEY=n WHERE ID IN ( %0 ), similar_set )This is not a good fit for SQL. But it is a good fit for all-in memory.