Function Calls

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Data Structures #◇Time Complexity #◇Space Complexity

◇Overview

Function calls require counting both the call itself and the operations inside the function.

◇Details / Theory

Function calls require counting both the call itself and the operations inside the function.

Rules:

Count 1 for the function call operation Count all operations within the function Add any parameter evaluation counts

Example:

sum = add(a, b)     // Count: 1 (for call) + operations inside add()

◇Special Cases and Advanced Counting

Summation for Variable Bounds

When a loop's bounds depend on another variable (like in nested loops with variable inner bounds), use summation notation:

For a loop like:

for i = 1 to n
    for j = 1 to i
        print(i,j)

The inner loop count needs summation:
Loop header: Σ(i+1) from i=1 to n Loop body: Σi from i=1 to n

Use summation formulas:
Σ(1) from i=1 to n = n Σ(i) from i=1 to n = n(n+1)/2 Σ(i²) from i=1 to n = n(n+1)(2n+1)/6

Analyzing Complex Nested Loops

For the example:

for i = 2 to n+1            // Count: n+1
    for j = 3 to n-3        // Count: (n-4)(n)
        for k = 4 to n-4    // Count: (n-6)(n-5)(n)
            x = x + 1       // Count: (n-7)(n-5)(n)

Total: n+1 + (n-4)(n) + (n-6)(n-5)(n) + (n-7)(n-5)(n) = n+1 + n²-4n + n³-11n²+30n + n³-12n²+35n = 2n³-22n²+62n+1

◇Key Formulas Reference

Simple Summations

Σ(1) from k=1 to n = n Σ(c) from k=1 to n = cn Σ(k) from k=1 to n = n(n+1)/2 Σ(k²) from k=1 to n = n(n+1)(2n+1)/6

Loops

For loops: header = ub-lb+2, body = ub-lb+1 per statement While (x ≤ ub): header = ub-lb+2, body = ub-lb+1 per statement While (x < ub): header = ub-lb+1, body = ub-lb per statement Do-while (x ≤ ub): condition = ub-lb+1, body = ub-lb+1 per statement Do-while (x < ub): condition = ub-lb, body = ub-lb per statement

◇Complexity

◇Common Pitfalls

Forgetting to count operations inside the called function. Miscounting nested loop bounds that depend on outer loop variables — use summation formulas. Mixing up loop header vs loop body counts for different loop types (for, while, do-while).

◇Summary

TL;DR — Function call frequency counting = 1 for the call itself + all operations inside the function. For nested loops with variable bounds, use summation formulas ($\sum i$, $\sum i^2$, etc.).

◇Links

Related: Source / Reference:

◇References & Navigation

• Previous Topic: ◇Frequency Count
• Next Topic: ◇Growth Rates
• Related Notes: ◇Recursion Tree Method, ◇Stacks