Time Complexity: Apply functions on matrices
O(n * m)
0
0
Apply functions on matrices in R Programming - Time & Space Complexity
Understanding Time Complexity
When we apply functions on matrices in R, we want to know how the time to run the code changes as the matrix gets bigger.
We ask: How does the work grow when the matrix size grows?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
m <- matrix(1:10000, nrow=100, ncol=100)
result <- apply(m, 1, sum) # sum each row
This code sums each row of a matrix with 100 rows and 100 columns.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Summing elements in each row of the matrix.
- How many times: The sum operation repeats once for each row (100 times here).
How Execution Grows With Input
As the matrix grows, the time to sum each row grows with the number of rows and columns.
| Input Size (n x n) | Approx. Operations |
|---|---|
| 10 x 10 | 100 sums (10 rows x 10 columns) |
| 100 x 100 | 10,000 sums (100 rows x 100 columns) |
| 1000 x 1000 | 1,000,000 sums (1000 rows x 1000 columns) |
Pattern observation: The total work grows roughly by the square of the matrix size because each element is visited once.
Final Time Complexity
Time Complexity: O(n * m)
This means the time grows proportionally to the number of rows times the number of columns in the matrix.
Common Mistake
[X] Wrong: "Applying a function on rows only depends on the number of rows."
[OK] Correct: Each row operation processes all columns, so columns also affect the time.
Interview Connect
Understanding how function application scales on matrices helps you reason about data processing tasks and optimize code in real projects.
Self-Check
"What if we applied the function on columns instead of rows? How would the time complexity change?"