Analyse The Efficiency and Correctness of an Algorithm

The correctness of an algorithms can be evaluated by using different methods.

• Unit tests
• Use a loop invariant

Unit Tests

import unittest
import PriyankaAndToys as pt
class UnitTest(unittest.TestCase):
    def test1(self):
        weights = [1, 2, 3, 21, 7, 12, 14, 21]
        self.assertEqual(pt.toys(weights), 4)
    def test2(self):
        weights = [1, 2, 3, 4, 5, 10, 11, 12, 13]
        self.assertEqual(pt.toys(weights), 2)
    def test3(self):
        weights = [1, 10, 20, 30, 40, 50, 60]
        self.assertEqual(pt.toys(weights), 7)
    def test4(self):
        weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        self.assertEqual(pt.toys(weights), 2)

By running these test, you can identify that the algorithm works fine and produce the expected outputs.

Loop Invariant

The next method that we can use to evaluate the correctness of the algorithm is to use a loop invariant.

We can use a condition or a statement as a loop invariant to measure the correctness of the algorithm. Let’s use a loop invariant in our algorithm.

The code looks like this.

def toys(weights):
    containers = 1
    weights.sort()
    current_weight = weights[0]
    for weight in weights:
        if not (weight <= current_weight + 4):
            containers = containers + 1
            current_weight = weight
    return containers

What is the loop invariant?

loop invariant = weight of each item in container must be less than the (minimum weight + 4) value in the container in each iteration.

How this works?

since the list of weights are sorted, we can assure that all the values that are next to a value are greater. So when we iterate through the list, we can keep the first value that comes into the container as the minimum value.

Now we can go through the list and check whether the loop invariant is satisfied in each iteration.

In our case, it does and we can assure that the algorithm is correct.

Let’s take a look at the efficiency of the algorithm.

Efficiency

In our algorithm, we definitely need to go through each and every item in the list to categorize them into the containers. For this the time complexity will be O(n) if the length of the list is n.

As you can see, the algorithm uses a sorting function to sort the list. There are different methods that can be used to sort a list. Each sorting technique has different running time complexities.

For example:

Selection sort – O(n^2)
Merge sort – O(n log (n))
Quick sort – O(n log (n))
Radix sort – O(nk)

def toys(weights):
    containers = 1
    weights.sort() # n log n
    current_weight = weights[0]
    for weight in weights:                      # n
        if not (weight <= current_weight + 4):  # n
            containers = containers + 1         # n
            current_weight = weight             # n
    return containers

So the total time complexity will be n log n + n. So as you can see the efficiency of the algorithm changes according to the sorting algorithm.

Also the efficiency will depend on the programming language we use to code. In the example of Prinyanka’s Toys, I have used python. But if you can use C++ or C which are really efficient programming languages, you can increase the efficiency of the algorithm.

This may not be reflected with an array of 100 items. But if you can increase the length of the array to hundred thousand of items, you will identify significant differences between the usages of the programming languages like c++ and also usage of different algorithms for sorting.

Thank you.