Analyzing Control Structures

Grokking Algorithm Complexity and Big-O

Ask Author

Back to course home

0% completed

Table of Contents

Loops and Time Complexity

Single Loop

Nested Loops

Consecutive Loops

Conditionals and Time Complexity

Summary of Control Structures and Their Complexities

Key Points to Remember

In programming, control structures like loops, conditionals, and nested structures define the flow of an algorithm. Understanding how these structures impact time complexity is essential to analyzing and optimizing code.

1. Loops and Time Complexity

Loops are among the most common control structures in algorithms. They repeat code for a certain number of times, so they significantly impact time complexity based on the number of iterations.

Single Loop

A single loop that runs n times has a time complexity of $O(n)$ because it scales linearly with the input size.

Python3

. . . .

Step Breakdown:

The for loop runs n times, where n is the size of the input.
The print(i) statement executes once for each loop iteration.

So, the total number of steps is equal to n because each line inside the loop runs n times.

Nested Loops

Nested loops involve loops within loops. Their time complexity is often the product of the inner and outer loop counts.

Python3

. . . .

Step Breakdown:

The outer loop runs n times.
For each iteration of the outer loop, the inner loop runs n times.
Therefore, the print(i, j) line runs n * n times.

In this case, the total number of steps would be n * n, or n².

Consecutive Loops

If loops run one after another, their time complexities are added.

Python3

. . . .

Step Breakdown:

The first loop runs n times, and the second loop runs m times.
The total number of steps is n + m.

The number of steps here depends on both n and m.

2. Conditionals and Time Complexity

Conditional statements (if, else, elif) help control the flow of an algorithm by executing certain parts of the code based on conditions.

Python3

. . . .

Step Breakdown:

There’s only one check (n > 10), which takes a single step.
Only one of the print statements runs, so that’s another single step.

Here, regardless of the input size, the total number of steps is always 2.

Summary of Control Structures and Their Complexities

Control Structure	Example	Time Complexity
Single Loop	`for i in range(n)`	$O(n)$
Nested Loop	`for i in range(n): for j in range(n)`	$O(n^2)$
Consecutive Loops	`for i in range(n); for j in range(m)`	$O(n + m)$
Conditional	`if x > 10`	$O(1)$
Conditional within Loop	`for i in range(n): if x > 10`	$O(n)$

Key Points to Remember

Loops Add Complexity: Loops increase complexity based on their depth and repetition rate.
Conditionals Are Constant: Single conditionals don’t add complexity based on input size, but they do within loops.
Recursive Calls Need Extra Analysis: Recursion can increase complexity quickly, especially if it involves multiple recursive calls.

In the next lesson, Analyzing Simple Algorithms, we’ll apply these concepts to real algorithms and learn how to find their time complexities step by step.

Mark as Completed

Table of Contents

Loops and Time Complexity

Single Loop

Nested Loops

Consecutive Loops

Conditionals and Time Complexity

Summary of Control Structures and Their Complexities

Key Points to Remember