Basic Principles of Time Complexity Calculation

• Elementary operations are considered constant time, denoted as O(1)
• Sequential structures combine time complexities through addition
• Loops multiply time complexities
• Branching structures take the maximum complexity among branhces
• When analyzing an algorithm's efficiency, focus primarily on the highest-order term
• Unless specified otherwise, we typically refer to worst-case time complexity

Single Loop Time Complexity Analysis

Example Problems

Example 1:

i = n*n;
while(i != 1)
    i = i/2;

We observe that the loop runs until i becomes 1, and in each iteration, i is halved.

Let’s denote the number of iterations as t and derive the relationship between t and the final value of i:

| **Number of Iterations (t)** | 0 | **1** | **2** | **3** | |---|---|---|---|---| | **Value of i** | | | | |

Step 2: Derive the mathematical relationship between t and i:

Step 3: Identify the stopping condition:

Step 4: Solve the equation derived from steps 2 and 3:

Taking logarithm base 2 on both sides gives:

Thus, the time complexity is:

Example 2:

x = 0;
while (n >= (x+1)*(x+1))
    x = x+1;

Step 1: List the number of iterations t and the final value of x:

| Number of Iterations (t) | 0 | 1 | 2 | 3 | |---|---|---|---|---| | Final Value of x | 0 | 1 | 2 | 3 |

Step 2: Establish the relationship between t and x:

Step 3: Define the loop termination condition:

Step 4: Combine equations from steps 2 and 3 to solve:

Hence, the time complexity is:

Example 3:

int i = 1;
while (i <= n)
    i = i * 2;

Step 1: Create a table showing the number of iterations t and final value of i:

| **Iterations (t)** | 0 | **1** | **2** | **3** | |---|---|---|---|---| | **Value of i** | **1** | **2** | **4** | **8** |

Step 2: Find the relationship between t and i:

Step 3: Identify the stop condition:

Step 4: Combine the two expressions to derive the result:

Therefore, the time complexity is:

Example 4:

int i = 0;
while (i*i*i <= n)
    i++;

Step 1: Record the number of iterations t and corresponding value of i:

| **Iterations (t)** | 0 | **1** | **2** | **3** | |---|---|---|---|---| | **Value of i** | 0 | **1** | **2** | **3** |

Step 2: Derive the relation between t and i:

Step 3: Determine the loop termination criterion:

Step 4: Solve the resulting equations:

Therefore, the time complexity is:

Example 5:

y = 0;
while ((y+1)*(y+1) <= n)
    y = y+1;

Step 1: Document the number of iterations t and final value of y:

| Iterations (t) | 0 | 1 | 2 | 3 | |---|---|---|---|---| | Final Value of y | 0 | 1 | 2 | 3 |

Step 2: Establish the relationship between t and y:

Step 3: Identify the stopping condition:

Step 4: Solve the system of equations:

Thus, the time complexity is:

Nested Loop Time Complexity

For nested loops, treat the outer loop as a single loop where its body contains another loop. This simplifies the calculation of time complexity.

Example Problems

Example 1:

int m = 0, i, j;
for (i=1; i<=n; i++)
    for(j=1; j<=2*i; j++)
        m++;

Step 1: Identify the outer loop iteration count:

Step 2: Determine inner loop execution counts per outer loop iteration:

| Outer Loop Iteration | 1 | 2 | 3 | …… | n | |---|---|---|---|---|---| | Inner Loop Execution Count | 2 | 4 | 6 | …… | 2n |

Note: Each outer loop iteration contributes its inner loop count. Total complexity is the sum of all inner loop executions.

Step 3: Sum up and simplify the result

Example 2:

for (i=0; i<n; i++)
    for(j=0; j<m; j++)
        a[i][j] = 0;

Step 1: Define the outer loop iterations:

Step 2: List inner loop execution count per outer iteration:

| **Outer Loop Iteration** | **1** | **2** | **3** | **...** | **n** | |---|---|---|---|---|---| | **Inner Loop Execution Count** | **m** | **m** | **m** | **m** | **m** |

Step 3: Add all inner loop counts together

Example 3:

count = 0;
for (k=1; k<=n; k*=2)
    for(j=1; j<=n; j++)
        count++;

Step 1: Determine how many times the outer loop runs:

Step 2: For each outer loop iteration, list inner loop execution count:

Since the number of outer loop iterations isn’t immediately obvious, compute it first:

| **Outer Loop Iteration** | **1** | **2** | **3** | **……** | | |---|---|---|---|---|---| | **Value of k** | **1** | **2** | **4** | **……** | **n** | | **Inner Loop Execution Count** | **n** | **n** | **n** | **n** | **n** |

Each inner loop executes n times. So total execution is:

Step 3: Sum all inner loop counts

Example 4:

for (i=n-1; i>=1; i--)
    for(j=1; j<=i; j++)
        if (A[j] > A [j+1])
            {// O(1) operation
}

Step 1: Define outer loop iterations:

Step 2: List inner loop execution count per outer iteration:

| **Outer Loop Iteration** | **1** | **2** | **3** | **...** | **n-1** | |---|---|---|---|---|---| | **Inner Loop Execution Count** | **n-1** | **n-2** | **n-3** | **...** | **1** |

Step 3: Sum all inner loop counts

This forms an arithmetic series, so the result is:

Multiple Nested Loops

Regardless of nesting depth, analyze each level separately and sum up the operations in the innermost loop.

Example:

for(i=0; i<=n; i++)
for(j=0; j<=i; j++)
for(k=0; k 0; --end)
{
int exchange = 0;

for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}

if (exchange == 0)
break;
}
}

Best case: N operations. Worst case: N(N+1)/2 operations. The complexity is O(N²)

Example 6

// Analyze the time complexity of BinarySearch?
int BinarySearch(int* a, int n, int x)
{
assert(a);

int begin = 0;
int end = n-1;
while (begin < end)
{
int mid = begin + ((end-begin)>>1);

if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid;
else return mid;
}
return -1;
}

Best case: 1 operation. Worst case: O(log N) operations. Complexity is O(log N)

Note: log N refers to base-2 logarithm. Sometimes expressed as lg N, but not recommended. Visualize with binary search on paper to understand the concept.

Example 7

// Analyze the time complexity of recursive factorial Fac?
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}

The recursion occurs N times. Time complexity is O(N)

Example 8

// Analyze the time complexity of recursive Fibonacci Fib?
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}

Recursion tree shows exponential growth. Time complexity is O(2^N). (Visualize with recursion stack diagram)