Introduction:

• Function Expression is a mathematical function (or expression) that represents how many operations an algorithm performs in terms of input size n.
• A function expression can be either exact or nearly exact, depending on whether the analysis is detailed (counting all operations) or asymptotic (focusing only on growth rate and dominant terms).
• It is also called the growth function or cost function f(n) .
• Function Expression is represented by f(n), where n is the size of the input.
• For Example: For a loop running n times ,
  • f(n) = 3n + 2
• Use of Function Expression :
  • Check performance: It helps us see how many steps a program takes when the input grows.
  • Find time complexity: It is used to convert the total steps into Big O form (like O(n), O(n²)).
  • Compare programs: Helps us know which program or algorithm runs faster.
  • Find slow parts: Shows which part of the code takes the most time and needs improvement.

Steps to Calculate Function Expression:

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

  • Determine what changes with the size of the input.
  • Usually, this is denoted as n.
  • Example:

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

    • Here, loop depends on n.

• 2. List the key operations

  • Count each basic instruction or operation that contributes significantly to runtime.
  • For example:
    • Assignment (=) → 1 operation
    • Comparison (<,>, ==) → 1 operation
    • Arithmetic (+, -, *, /) → 1 operation
    • Function call → 1 operation

• 3. Count how many times each operation executes

  • Example:
    

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

    • int i = 0 → runs 1 time.
    • i <= n → runs n+1 times (last check fails).
    • i++ → runs n times.
    • System.out.println("Hello"); → runs n times.

• 4. Add all operations together

  • Write the expression combining all operation counts. Example:
  • From the example above:
    

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

• 5. Simplify the expression (optional)

  • If you’re focusing on asymptotic analysis, keep only the dominant term (e.g., simplify 3n+2 to O(n)).
  • But if you want exact function expression, keep all terms.

Some Examples with their Function Expression:

• Example 1 : Single Loop

  • for (int i = 1; i <= n; i++)
    {
        System.out.println(i*2);
    }

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

• Example 2 — Nested Loops

  • for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            System.out.println("Hello");
        }
    }

    • Function Expression: f(n) = (2n+2) + n*(3n+2) → 3n² + 4n + 2
    • Nearly exact f(n): (outer loop cost) × (inner loop cost) → f(n): 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 — Rectangular Loops (Different Variables)

  • for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            System.out.println("Hello");
        }
    }

    • Function Expression: f(n, m) = (2n+2) + n*(3m + 2) → 3nm + 4n + 2