While printing might introduce minor variations, in Big O notation, we ignore constant factors and focus on the dominant term, which is log n in this case.

Example 5:

int i;
i = j = 0;
for (i ; i < n; i ++)
    for (j; j < n; j = j / 3)
    print i + j;

Let’s analyze the time complexity of the provided code, considering both inner and outer loops:

Outer loop:

• Iterates n times (for i from 0 to `n-1)
• Performs constant time operations:
  – Incrementing i

Inner loop:

• Nested inside the outer loop, so executes n times for each iteration of the outer loop (total of n^2 executions)
• Iterates while j is less than n
• Divides j by 3 in each iteration (decreasing by a factor of 3)
• Performs constant time operations:
  – Checking the condition j < n
  – Division (j = j / 3)
  – Adding i + j (assuming addition and printing are constant time)

Key observation:

The inner loop’s condition (j < n) ensures j eventually becomes 0 or less due to the division by 3. This means the loop terminates within a finite number of steps.

Number of iterations in the inner loop:

• In the first iteration, j = 0, so it terminates immediately.
• In subsequent iterations, j starts with the final value from the previous outer loop iteration (1, 2, …).
• Since j is divided by 3 in each iteration, the number of iterations needed to reach 0 or less depends on the starting value and its divisibility by 3.
• The worst-case scenario occurs when j is not divisible by 3 (e.g., 2, 5, 8, …).
• In this case, it takes log3(j) iterations to reach 0 (approximately log3(n) for large n).

Overall complexity:

• The outer loop runs n times (O(n)).
• The inner loop runs a maximum of log3(n) times per outer loop iteration.
• Combining these, the total worst-case complexity becomes O(n * log3(n)).

However, there’s a subtle point to consider:

• When j is divisible by 3 in certain outer loop iterations, the inner loop terminates faster than log3(n).
• Averaging across all possible starting values of j, the actual number of iterations per outer loop might be slightly lower than log3(n).

Therefore, a more accurate complexity representation could be O(n * log3(n)^α), where α is a factor between 0 and 1 reflecting the average behavior compared to the worst-case scenario.

In conclusion, the code’s time complexity is roughly O(n * log3(n)), though the exact constant factor might vary depending on the average divisibility of starting values in the inner loop.

Example 6:

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k = k * 2)
            print i + j + k;

This code has three nested loops, so let’s analyze each one to understand its overall complexity:

Outer loop:

• Iterates n times (for i from 0 to n-1).

Middle loop:

• Nested inside the outer loop, so executes n times for each iteration of the outer loop (total of n^2 executions).
• Iterates n times (for j from 0 to n-1).

Inner loop:

• Nested within the middle loop, so executes n^2 times in total.
• Iterates while k is less than n and doubles k in each iteration.

Understanding the inner loop:

• k keeps doubling until it reaches or exceeds n.
• Doubling happens repeatedly, but eventually, even large starting values of k will become bigger than n after a finite number of doublings. This number of doublings can be approximated by the logarithm base 2 of n (log2(n)).

Combining complexities:

• Outer loop contributes O(n).
• Middle loop contributes another O(n) factor.
• Inner loop contributes O(log2(n)) per outer-middle loop iteration.

Overall complexity:

• Total complexity is O(n * n * log2(n)), which simplifies to O(n^2 * log2(n)).

Interpretation:

• This means the execution time will grow quadratically with input size n due to the n^2 term.
• Additionally, the logarithmic term (log2(n)) introduces a slower-growing increase in execution time compared to a pure quadratic function.

Simple analogy:

Imagine filling a square box with smaller boxes. With n rows and columns, you have n^2 boxes. Now, within each box, you put objects that double in number until they fill the box. The total number of objects will grow like n^2 * log2(n), reflecting both the initial boxes and the doubling growth within each box.

Example 7:

for (int i = n / 2; i < n; i++)    // n / 2
    for (int k = 0; k < n; k = k * 2)    // log n
        for (int j = 0; j < n; j = j * 2)    // log n
            print i + k + j;

Total:

n/2 * log n * log n

n * log n * log n

n * log2(n)^2

The complexity will be O(n*log2(n)^2)

Fibonacci Sequence

Fibonacci numbers are a fascinating sequence in mathematics where each number is the sum of the two preceding ones. The sequence starts with 0 and 1, so the first few Fibonacci numbers are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Generating the sequence:

• You can define the sequence recursively as:
  – F(0) = 0
  – F(1) = 1
  – F(n) = F(n-1) + F(n-2) for n > 1

Example 8:

int fib(int n) {
if (n < 2)
return n;
return fib(n - 1) + fib(n - 2); }

In Big O notation, O(2^n) signifies that the execution time grows proportionally to 2 raised to the power of n.