As described in the slides, the outer for loop statements account for
4⌈log 2 n⌉
, and the total contribution of the inner loop is at least
8 12 8n−12
. Thus, the total running time is at least (Then the two complexities are added instead of multiplied to each other)
So it’s O(nlog(n)) and not log(n)
Course: https://www.educative.io/courses/big-o-notation-cpp
Lesson: Educative: Interactive Courses for Software Developers