Code generation for C/C++ in MATLAB - Time & Space Complexity

Time Complexity: Code generation for C/C++

O(n)

Understanding Time Complexity

When generating C/C++ code from MATLAB, it is important to understand how the time needed to run the generated code grows as the input size increases.

We want to know how the execution time changes when the input data gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following MATLAB code that will be converted to C/C++.

function y = sumArray(x)
  y = 0;
  for i = 1:length(x)
    y = y + x(i);
  end
end

This code sums all elements in an array x by looping through each element once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each element of the array to a total sum.
• How many times: The loop runs once for every element in the input array.

How Execution Grows With Input

As the input array gets bigger, the number of additions grows in the same way.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The number of operations grows directly with the size of the input.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the code grows in a straight line as the input size increases.

Common Mistake

[X] Wrong: "The loop runs faster because it is simple, so time does not grow much with input size."

[OK] Correct: Even a simple loop takes more time when it runs more times. The total time depends on how many elements are processed.

Interview Connect

Understanding how loops affect time helps you explain how your code will perform when converted to C/C++. This skill shows you can think about efficiency beyond just writing code.

Self-Check

"What if we replaced the loop with a built-in MATLAB function that sums the array? How would the time complexity change?"

Practice

1. What is the primary purpose of using codegen in MATLAB for C/C++?

easy

A. To visualize MATLAB data in 3D plots

B. To debug MATLAB scripts line by line

C. To create graphical user interfaces in MATLAB

D. To convert MATLAB code into C/C++ code for faster execution or integration

Solution

1. Step 1: Understand the role of codegen

   codegen is used to generate C/C++ code from MATLAB functions.

2. Step 2: Identify the main benefit

   This conversion helps in faster execution and easier integration with other C/C++ projects.

3. Final Answer:

   To convert MATLAB code into C/C++ code for faster execution or integration -> Option D

4. Quick Check:

   Code generation = convert MATLAB to C/C++ [OK]

Hint: Remember: codegen means generate code in C/C++ [OK]

Common Mistakes:

• Confusing codegen with debugging tools
• Thinking codegen creates plots
• Assuming codegen builds GUIs

2. Which of the following is the correct syntax to generate C code for a MATLAB function myFunc with input type double scalar?

easy

A. codegen myFunc -args {double(0)}

B. codegen myFunc -args {single(1)}

C. codegen myFunc -args {int32(1)}

D. codegen myFunc -args {1+0i}

Solution

1. Step 1: Understand input argument specification

   For codegen, input types are specified using MATLAB data types like double(0) for a scalar double.

2. Step 2: Check each option

   codegen myFunc -args {double(0)} uses double(0) which correctly specifies a double scalar input. Others either use incorrect syntax or values.

3. Final Answer:

   codegen myFunc -args {double(0)} -> Option A

4. Quick Check:

   Input type double scalar = double(0) [OK]

Hint: Use double(0) to specify a double scalar input [OK]

Common Mistakes:

• Using numeric literals directly without type
• Using curly braces incorrectly
• Confusing input value with input type

3. Given the MATLAB function

function y = squarePlusOne(x)
y = x.^2 + 1;
end

What will be the output C code function signature generated by codegen squarePlusOne -args {zeros(3,1)}?

medium

A. void squarePlusOne(const double x[3], double y[3])

B. double squarePlusOne(double x)

C. void squarePlusOne(double x, double *y)

D. double squarePlusOne(const double x[3])

Solution

1. Step 1: Analyze input argument

   The input is a 3x1 double vector, so the generated C function will take an array of 3 doubles as input.

2. Step 2: Determine output type

   The output is also a 3x1 vector, so the output is an array passed by reference.

3. Step 3: Match function signature

   void squarePlusOne(const double x[3], double y[3]) matches the expected signature: void function with input array and output array parameters.

4. Final Answer:

   void squarePlusOne(const double x[3], double y[3]) -> Option A

5. Quick Check:

   Array input/output = void func(const double x[3], double y[3]) [OK]

Hint: Array inputs generate functions with array parameters [OK]

Common Mistakes:

• Assuming scalar input/output signatures
• Missing const qualifier for input arrays
• Returning output instead of using output parameter

4. You try to generate C code for this MATLAB function:

function y = addVectors(a, b)
y = a + b;
end

using codegen addVectors -args {zeros(3,1), zeros(4,1)}. What is the main issue?

medium

A. Function syntax is incorrect for code generation

B. Input vectors have different sizes causing a code generation error

C. You must specify input types as integers, not doubles

D. codegen cannot handle vector inputs

Solution

1. Step 1: Check input argument sizes

   The inputs are vectors of sizes 3x1 and 4x1, which cannot be added element-wise due to size mismatch.

2. Step 2: Understand codegen requirements

   Code generation requires consistent input sizes for operations like addition.

3. Final Answer:

   Input vectors have different sizes causing a code generation error -> Option B

4. Quick Check:

   Size mismatch in inputs = error [OK]

Hint: Ensure input sizes match for element-wise operations [OK]

Common Mistakes:

• Ignoring input size mismatch
• Assuming codegen auto-resizes inputs
• Confusing data type with size issues

5. You want to generate C++ code from this MATLAB function that computes the sum of positive elements only:

function s = sumPositive(v)
s = sum(v(v > 0));
end

Which input argument specification is best for codegen to handle variable-length vectors?

hard

A. codegen sumPositive -args {double(0)}

B. codegen sumPositive -args {zeros(10,1)}

C. codegen sumPositive -args {coder.typeof(0,[Inf,1],[1,0])}

D. codegen sumPositive -args {coder.typeof(0,[10,1],[0,0])}

Solution

1. Step 1: Understand variable-size input specification

   To handle variable-length vectors, coder.typeof with [Inf,1] size and [1,0] variable-size flags is used.

2. Step 2: Evaluate options

   codegen sumPositive -args {coder.typeof(0,[Inf,1],[1,0])} correctly specifies a variable-length column vector of doubles. Others specify fixed sizes or scalars.

3. Final Answer:

   codegen sumPositive -args {coder.typeof(0,[Inf,1],[1,0])} -> Option C

4. Quick Check:

   Variable-size vector = coder.typeof with Inf size [OK]

Hint: Use coder.typeof with Inf size for variable-length inputs [OK]

Common Mistakes:

• Using fixed-size arrays for variable-length inputs
• Not setting variable-size flags correctly
• Confusing scalar input with vector input