Introduction:

• Function Expression is a mathematical formula that represents the number of basic operations an algorithm performs based on the input size n.
• It is also called the growth function or cost function f(n) .
• It helps to describe the exact number of steps before simplifying into time complexity.
• Example: For a loop running n times ,
  • f(n) = n
• Use of Function Expression :
  • Analyzes Performance: Shows how the number of steps grows with input size.
  • Basis for Time Complexity: Used to convert into Big-O notation.
  • Algorithm Comparison: Helps decide which algorithm is faster for large inputs.
  • Optimization Insight: Identifies which parts of code are most expensive.

Steps to Calculate Function Expression:

• 1. Identify the input size variable (usually n)

  • Find the variable that changes with the size of the input.
  • Example:

    for (int i = 0; i < n; i++)
    {
        System.out.println("Hi");
    }

    • Input size variable = n (loop depends on it).

• 2. Assign a cost (usually 1) to each basic operation

  • Basic operations:
    • Assignment (=) → cost = 1
    • Comparison (<,>, ==) → cost = 1
    • Arithmetic (+, -, *, /) → cost = 1
    • Function call → cost = 1
  • Example:
    i = 0; → cost = 1 unit.

• 3. Count how many times each operation runs for input size n

  • Example:
    

    for (int i = 0; i < n; i++)
    {
        sum += i;
    }

    • i = 0 → runs 1 time.
    • i < n → runs n+1 times (last check fails).
    • i++ → runs n times.
    • sum += i → runs n times.

• 4. Add them together to get total cost → f(n)

  • From the example above:
    

    f(n) = 1        // initialization
         + (n + 1)  // comparisons
         + n        // increments
         + n        // sum operations
    f(n) = 3n + 2

Some Examples with their Function Expression:

• Example 1 : Single Loop

  • for (int i = 0; i < n; i++)
    {
        sum += i;
    }

    • Function Expression: f(n) = 3n + 2

• Example 2 — Nested Loops (Square Complexity)

  • for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            sum += i + j;
        }
    }

    • Function Expression: f(n) = n² + 2n² + n² → 4n²
    • Here: (outer loop cost) × (inner loop cost) → n × n = n².
    • In nested loops, the inner loop runs completely for each iteration of the outer loop, so we multiply the costs of both loops.

• Example 3 — Nested Loops with Extra Single Loop

  • for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            sum += i + j;
        }
    }
    for (int k = 0; k < n; k++)
    {
        sum += k;
    }

    • Function Expression: f(n) = 4n² + 3n + 2
    • (First part → 4n², Second part → 3n + 2)
    • When we have nested loops first and then a separate non-nested loop, we add their function expressions.
    • Rule: Multiplication for nested loops, Addition for separate loops.

• Example 4 — Rectangular Loops (Different Variables)

  • for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            sum += i + j;
        }
    }

    • Function Expression: f(n, m) = 3nm + n + 1

• Example 5 — Loop with Inner Loop Depending on Outer Index

  • for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            sum += i + j;
        }
    }

    • Function Expression:
      

       f(n) = (n(n+1))/2 * cost_inside
            = (n² + n)/2 * 3
            = (3n² + 3n)/2