Logarithmic time

 

Logarithmic time

So earlier, when discussing the number of times a binary search repeats itself, we asked the question 2^? = n.

The answer would be log₂n - the base 2 logarithm of n. This function grows very slowly with respect to n and so logarithmic time algorithms are extremely desirable.

We can therefore classify binary search (any many other divide and conquer algorithms) as O(log n)

In computer science, logarithmic time is a measure of the efficiency of an algorithm, where the running time of the algorithm increases logarithmically with the size of the input.

The logarithmic function is a mathematical function that grows very slowly as the input size increases. For example, the logarithm of a million (1,000,000) to base 2 is just 20, because 2^20 equals 1,000,000. This means that the running time of an algorithm with logarithmic time complexity will increase very slowly as the size of the input grows.

An algorithm with logarithmic time complexity is generally considered to be very efficient, as it can handle large inputs without a significant increase in running time.

An example of an algorithm with logarithmic time complexity is binary search, which is a divide and conquer algorithm used to search for a specific element in a sorted list. Binary search has a time complexity of O(log n), where n is the number of elements in the list. This means that the running time of the algorithm increases very slowly as the size of the input grows.

In general, logarithmic time algorithms are very efficient and are well-suited for problems where the input size may be large. However, they may not be the most efficient choice for problems with small input sizes, due to the overhead of the logarithmic function.

Exercises

Try to implement some of the algorithms discussed in this class, using a programming language of your choice:

●     The three problems at the beginning

●     An anagram algorithm (preferably fast)

●     A divide and conquer algorithm - perhaps to find out the lowest value of n for which a + bn + cn² is less than (c+1)n²

○     Is there a faster way of doing this?

Solutions

1.       Given three integers a, b, and c, check if a + b = c:

# Initialize variables a, b, and c

a = 2

b = 3

c = 5

 

# Check if a + b equals c

if a + b == c:

    # If a + b equals c, print "True"

    print("True")

else:

    # If a + b does not equal c, print "False"

    print("False")

This solution has a time complexity of O(1), as it only requires a single comparison operation.

2.       Given a set of integers S = {a, b, c, ...} and an integer k, find out if all elements of S add up to k:

# Initialize list S and integer k

S = [1, 2, 3, 4]

k = 10

 

# Initialize variable sum to 0

sum = 0

 

# Iterate through elements in S

for i in S:

    # Add element to sum

    sum += i

 

# Check if sum equals k

if sum == k:

    # If sum equals k, print "True"

    print("True")

else:

    # If sum does not equal k, print "False"

    print("False")

This solution has a time complexity of O(n), where n is the number of elements in the set S. It requires one pass through the list S to add up the elements.

3.       Given a set of integers S = {a, b, c, ...} and an integer k, find out if any subset of S adds up to k:

# Initialize list S and integer k

S = [1, 2, 3, 4]

k = 10

 

# Initialize variable found to False

found = False

 

# Iterate through elements in S

for i in S:

    # Check if element equals k

    if i == k:

        # If element equals k, set found to True and break loop

        found = True

        break

    # If element does not equal k, check if element plus k is in S

    elif (k - i) in S:

        # If element plus k is in S, set found to True and break loop

        found = True

        break

 

# Print found

print(found)

This solution has a time complexity of O(n), where n is the number of elements in the set S. It requires one pass through the list S

Looking at the third problem:

●     Given a set of integers S and an integer k, find out if any subset of S adds up to k

Consider a related problem:

●     Given two sets of integers, S and W, and an integer k, find out if W is a subset of S which adds up to k

Is one problem easier to solve than the other? Can you produce an algorithm? What is it’s time complexity?

The second problem is generally easier to solve than the first problem, because it only requires us to check if a single subset of S adds up to k, rather than any subset of S.

Here is an algorithm to solve the second problem:

1.       Sort the set W in ascending order.

2.       Iterate through elements in W.

3.       At each element, check if it equals k. If it does, return True.

4.       If the element does not equal k, check if k - element is in S. If it is, return True.

5.       If the element is not in S and does not equal k, continue to the next element in W.

6.       If the end of W is reached, return False.

This algorithm has a time complexity of O(n log n), where n is the number of elements in the set W. This is because the algorithm requires one pass through the sorted list W, and the list W is sorted using a sorting algorithm with time complexity O(n log n).

Here is an example implementation of the algorithm in Python:

# Initialize sets S and W and integer k

S = [1, 2, 3, 4]

W = [2, 3]

k = 5

 

# Sort the set W in ascending order

W.sort()

 

# Iterate through elements in W

for i in W:

    # Check if element equals k

    if i == k:

        # If element equals k, print "True" and exit loop

        print("True")

        break

    # If element does not equal k, check if k - element is in S

    elif (k - i) in S:

        # If k - element is in S, print "True" and exit loop

        print("True")

        break

 

# If the end of W is reached, print "False"

print("False")

here is the example implementation again starting from the point where the set W is sorted:

# Sort the set W in ascending order

W.sort()

 

# Iterate through elements in W

for i in W:

    # Check if element equals k

    if i == k:

        # If element equals k, print "True" and exit loop

        print("True")

        break

    # If element does not equal k, check if k - element is in S

    elif (k - i) in S:

        # If k - element is in S, print "True" and exit loop

        print("True")

        break

 

# If the end of W is reached, print "False"

print("False")

This code will iterate through the elements in the sorted set W. At each element, it will check if the element equals k or if k - element is in S. If either condition is met, the code will print "True" and exit the loop. If the end of the loop is reached, the code will print "False".

The first problem could be solved by trying every subset of S individually and comparing the sum of each subset to k. This would require the evaluation of 2ⁿ sets of integers. This is known as an exponential time algorithm (as the runtime grows exponentially with respect to the input size). Its runtime can be denoted by O(2ⁿ).

The consequences of this are huge - it means that the runtime doubles every time we add an extra element to the set. Build the most powerful computer in the world and all we need to do is find the biggest subset sum problem it can solve using this method, add a handful of extra integers to it and it will grind to a halt again!

We normally regard exponential time algorithms as a bad idea for this reason.

As a consequence it is generally accepted that not all algorithms are worth using - even algorithms that are totally correct can have such poor time complexities as to be useless in practice.

So in order to be usable, an algorithm needs not only to get the correct solution but also to get there before it’s user dies of old age (and his children and his children’s children...). In fact as we will learn later, we’re more likely to use an algorithm which runs quickly with an approximate answer than an exponential time algorithm.

For this reason, we need some notion of an efficient solution to a problem, as opposed to a merely accurate one.