Function and procedure in packages in VHDL - Time & Space Complexity

Time Complexity: Function and procedure in packages

O(n)

Understanding Time Complexity

We want to understand how the time needed to run functions and procedures inside VHDL packages changes as input size grows.

How does the number of operations grow when these packaged routines process larger inputs?

Scenario Under Consideration

Analyze the time complexity of the following VHDL package with a function and a procedure.

package Math_Pkg is
  type integer_array is array (natural range <>) of integer;
  function Sum_Array(arr : in integer_array) return integer;
  procedure Print_Array(arr : in integer_array);
end Math_Pkg;

package body Math_Pkg is
  function Sum_Array(arr : in integer_array) return integer is
    variable total : integer := 0;
  begin
    for i in arr'range loop
      total := total + arr(i);
    end loop;
    return total;
  end Sum_Array;

  procedure Print_Array(arr : in integer_array) is
  begin
    for i in arr'range loop
      report integer'image(arr(i));
    end loop;
  end Print_Array;
end Math_Pkg;

This package defines a function to sum elements of an integer array and a procedure to print each element.

Identify Repeating Operations

Look for loops or repeated steps inside the function and procedure.

• Primary operation: Both the function and procedure use a loop that goes through each element of the input array.
• How many times: The loop runs once for every element in the array, so if the array has n elements, the loop runs n times.

How Execution Grows With Input

As the input array gets bigger, the number of times the loop runs grows directly with the size.

Input Size (n)	Approx. Operations
10	10 loop iterations
100	100 loop iterations
1000	1000 loop iterations

Pattern observation: The number of operations grows in a straight line with the input size. Double the input, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the function or procedure grows directly in proportion to the number of elements in the input array.

Common Mistake

[X] Wrong: "The function or procedure runs in constant time because it just sums or prints values."

[OK] Correct: Even though the operations inside the loop are simple, the loop runs once for each element, so the total time depends on how many elements there are.

Interview Connect

Understanding how loops inside functions and procedures affect time helps you explain how your code scales, a key skill in real projects and interviews.

Self-Check

"What if the function used nested loops to sum elements in a two-dimensional array? How would the time complexity change?"

Practice

1. What is the main difference between a function and a procedure in a VHDL package?

easy

A. A procedure returns a value, while a function does not.

B. A function returns a value, while a procedure does not.

C. Both return values but differ in syntax.

D. Neither returns a value; both perform actions only.

Solution

1. Step 1: Understand function behavior

   A function in VHDL always returns a value and can be used in expressions.

2. Step 2: Understand procedure behavior

   A procedure performs actions but does not return a value directly.

3. Final Answer:

   A function returns a value, while a procedure does not. -> Option B

4. Quick Check:

   Function returns value = B [OK]

Hint: Functions return values; procedures do not [OK]

Common Mistakes:

• Thinking procedures return values
• Confusing syntax differences with return behavior
• Assuming both can be used in expressions

2. Which of the following is the correct way to declare a function inside a VHDL package?

easy

A. function add(a : integer; b : integer) return integer;

B. procedure add(a : integer; b : integer) return integer;

C. function add(a, b : integer);

D. procedure add(a : integer; b : integer);

Solution

1. Step 1: Check function declaration syntax

   A function must specify parameters with types and a return type using return.

2. Step 2: Validate options

   function add(a : integer; b : integer) return integer; correctly declares a function with parameters and return type. Options A and B are procedures, and C misses return type.

3. Final Answer:

   function add(a : integer; b : integer) return integer; -> Option A

4. Quick Check:

   Function declaration needs return type = D [OK]

Hint: Functions must declare return type explicitly [OK]

Common Mistakes:

• Using 'procedure' keyword for functions
• Omitting return type in function declaration
• Adding return type to procedures

3. Given the following package body code, what is the output of calling result := math_pkg.multiply(3, 4);?

package body math_pkg is
  function multiply(x : integer; y : integer) return integer is
  begin
    return x * y;
  end multiply;
end math_pkg;

medium

A. 12

B. 7

C. Error: function not found

D. 0

Solution

1. Step 1: Understand function multiply

   The function returns the product of x and y, so multiply(3,4) returns 3*4 = 12.

2. Step 2: Confirm no errors

   The function is correctly declared and defined in the package body, so no errors occur.

3. Final Answer:

   12 -> Option A

4. Quick Check:

   3 * 4 = 12 [OK]

Hint: Multiply returns product of inputs [OK]

Common Mistakes:

• Confusing addition with multiplication
• Assuming function is undefined
• Expecting procedure behavior

4. Identify the error in this package declaration:

package util_pkg is
  procedure display_message(msg : in string);
  function get_length(msg : string) return integer;
end util_pkg;

medium

A. Package missing body keyword.

B. Procedure missing return type.

C. Function parameter missing mode (in/out).

D. Procedure parameter mode is incorrect.

Solution

1. Step 1: Check procedure parameter modes

   Procedure parameters must specify mode (in, out, inout). The procedure parameter msg correctly uses in.

2. Step 2: Check function parameter modes

   Function parameters must also specify mode explicitly. The function parameter msg : string lacks mode, which is required.

3. Final Answer:

   Function parameter missing mode (in/out). -> Option C

4. Quick Check:

   Function parameters need mode = A [OK]

Hint: Always specify parameter mode in functions and procedures [OK]

Common Mistakes:

• Omitting parameter mode in functions
• Confusing package and package body syntax
• Thinking procedures need return types

5. You want to create a VHDL package that includes a function to calculate the factorial of a number and a procedure to print the result. Which of the following is the best approach?

hard

A. Define factorial as a procedure modifying a global variable; print as a function returning string.

B. Define both factorial and print as functions returning integer.

C. Define factorial as a procedure returning integer; print as a procedure with no parameters.

D. Define the factorial as a function returning integer; define the print as a procedure taking integer input.

Solution

1. Step 1: Choose correct return types

   Factorial calculation returns a value, so it should be a function returning integer.

2. Step 2: Choose correct procedure for printing

   Printing is an action without return value, so it should be a procedure taking the integer to print.

3. Final Answer:

   Define the factorial as a function returning integer; define the print as a procedure taking integer input. -> Option D

4. Quick Check:

   Function returns value; procedure performs action = C [OK]

Hint: Use function for calculations, procedure for actions [OK]

Common Mistakes:

• Using procedures to return values
• Defining print as function with return value
• Not passing parameters to procedures