CISC 121 Lecture Notes - Lecture 30: Insertion Sort, Bubble Sort, Selection Sort

• School: Queen's University
• Department: Computing
• Course: CISC 121
• Professor: Wendy L Powley

Document Summary

We would still say this slight revision of the previous code snippet runs in. O(log n) time, even though it"s more precisely o(log3 n) time: n = len(some_list) log_n = 0 while n > 0: n = n // 3 if n > 0: log_n += 1. In this case n is being reduced by two-thirds at each pass through the loop. The general rule for deciding what big-o complexity level to award to nested loops is this: O(whole loop structure) = o(outer loop) x o(inner loop) Recognizing that the inner loop may itself contain a loop (which may, in turn, contain a loop, and so on). Thus, if the complexity of both outer and inner loops of a singly nested loop structure is o(n), the complexity of the whole is o(n2). And thus, if the inner loop itself has an inner loop (doubly nested) of complexity o(log n), the complexity of the whole is o(n2 log n).