7.4 Multiple parameters

Imagine that we want to keep track of friendships between n people. We can do this with a 2-dimensional array of size n \times n (a matrix). Each row of the matrix represents the friends of an individual, with the columns indicating who has that individual as a friend. For example, if person j is a friend of person i, then we place a mark in column j of row i in the array. Likewise, we should also place a mark in column i of row j if we assume that friendship works both ways. For n people, the total size of the matrix is in O(n^2).

But is this the best representation of friendship links? Assume that n grows large, and we want to include every person in Sweden (which has around 10 million people). Then the matrix will have around (10^7)^2 = 10^{14} cells. Instead of storing a n\times n matrix, we can store an array of size n with pointers to lists of numbers. Now, if array cell j points to a list containing i, then person j is a friend of person i. What is the total size of this data structure alltogether, in big-O notation?

This depends on how many friends people have, but let’s say that every person has m friends on average. We don’t know what m is, but we can be quite certain that it is a lot smaller than n. So, what can we say about the space complexity of this new data structure? One the one hand, the array contains n elements so the size is O(n), but on the other hand, each list uses on average O(m) memory.

We can of course assume that m is bounded, for example that it is at most 100 – then we can say that m is constant and then we get O(n) for the whole data structure. But this is cheating, because we cannot know how m changes when n grows. The big-O notation can used for multiple parameters at the same time, so we can write the space complexity of the new array-of-lists representation as O(n\times m) because it is linear in both n and m.

Now, what is the time complexity of testing if two given persons are friends with each other? That depends on the representation.

Matrix representation

We have a n\times n boolean matrix F such that F[i,j] is true if person i is friend with person j. But i and j are array indices and not persons, so we also need an array P of strings where we can look up persons a and b and find their indices i and j (so that a=P[i] and b=P[j]). If this array is sorted we can use binary search.

To test if a and b are friends, we have to find their indices i and j and then just lookup F[i,j]. Finding the indices is logarithmic in the number of people, and testing is constant. So the complexity is O(\log(n)), which is indepedent of the number of friends per person, m.

Array of lists

Now we have a size n array F' such that F'[i] is a list of the people that person i is friends with. We still need the array P for looking up the index of a person.

To test if a and b are friends, we find the index i of person a, which is logarithmic in n. Then we do a linear search for b in the list F'[i], which we all know is linear in the number of friends per person, m. So the complexity of testing friendship is O(m\cdot\log(n)).

for i in 0 .. c-1:        // Initialise the counts.
    count[i] = 0
for i in 0 .. p-1:        // Increment the colour value count for each pixel.
    count[value(i)] += 1
sort(count)               // Sort the pixel value counts.