O(log n) even when we create a new array? Not O(n)?

#1

Hi friends :slight_smile:

I am analyzing the time complexity of this example in the beginning of Chapter 11, Searching (page 147 in the Python book). The search portion is clearly O(log n), but wouldn’t the whole program have a longer runtime since we create a whole new array (O(n)) on which to operate before running the search? (O(n) since O(n) > O(log n).) From the book (please excuse lack of indentation):

Suppose we are given as input an array of students, sorted by descending GPA, with ties broken on name. In the program below, we show how to use the library binary search routine to perform fast searches in this array. In particular, we pass binary search a custom comparator which compares students on GPA (higher GPA comes first), with ties broken on name.

Student = collections.namedtuple(’Student’, (’name’, ’grade_point_average’))

def comp_gpa(student: Student):
return (-student.grade_point_average, student.name)

def search_student(students: List[Student], target: Student, comp_gpa: Callable[[Student], Tuple[float, str]]):
i = bisect.bisect_left([comp_gpa(s) for s in students], comp_gpa(target))
return 0 <= i < len(students) and students[i] == target

Assuming the i-th element in the sequence can be accessed in O(1) time, the time complexity of the program is O(log n).

Can someone help me understand why the solution is considered O(log n) if this is correct? Is there a property of Python lists which lets the remapping occur on access instead of on the entire input list? Love to hear your insight. Thank you!

0 Likes
#2

I found an approach that doesn’t require creating a new array, as Python 3.10 has added a named key param to bisect.bisect_left (https://docs.python.org/3/library/bisect.html#bisect.bisect_left).

Though the usage has slightly more applications, it’s a bit non-intuitive, since you have to call the key function on the target (see https://stackoverflow.com/questions/72101337).

This modified bisect_left call removes the need to create a new array in Python 3.10:

i = bisect.bisect_left(students, comp_gpa(target), key=comp_gpa)

0 Likes