1.5.2 Time Complexity Example #2 | Highlights and Annotations by Gistr.

This text analyzes time complexity of loops. Incrementing loops (i++, i+=2) are O(n). Loops where the counter is multiplied (i*=2, i*=3) are O(log n). A loop with `i*i <= n` is O(√n). Independent loops add their complexities; nested loops multiply them. Logarithm base is generally ignored in Big O notation. The choice between floor and ceiling for log n depends on the specific problem. This segment meticulously analyzes a loop where the counter variable is multiplied by two in each iteration, demonstrating how to determine its time complexity is logarithmic (O(log n)) by deriving the relationship between the number of iterations (k) and the loop termination condition (i >= n). The explanation clearly shows how 2 k >= n leads to k = log₂n. This segment effectively contrasts the time complexity of a standard linear loop (O(n)) with a loop where the counter variable is multiplied by two in each iteration (O(log n)). By stepping through both scenarios, the speaker highlights the key difference in how the number of iterations scales with the input size (n), providing a clear understanding of the impact of different loop structures on time complexity. This segment focuses on a loop where the counter variable is repeatedly divided by two. The speaker systematically determines the time complexity by showing how the loop's termination condition (i < 1) relates to the number of iterations (k) and the initial value of the counter (n). The analysis clearly demonstrates that the time complexity is also logarithmic (O(log n)), mirroring the previous example but with division instead of multiplication.