Time Complexity: lapply and sapply
O(n)
0
0
lapply and sapply in R Programming - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time taken by lapply and sapply grows as the input list gets bigger.
How does the number of operations change when we apply a function to many items?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
my_list <- list(1, 2, 3, 4, 5)
result_lapply <- lapply(my_list, function(x) x * 2)
result_sapply <- sapply(my_list, function(x) x * 2)This code applies a simple function to each item in a list using lapply and sapply.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Applying the function to each element in the list.
- How many times: Once for each element in the list (n times).
How Execution Grows With Input
As the list gets bigger, the function runs more times, one for each item.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 function calls |
| 100 | 100 function calls |
| 1000 | 1000 function calls |
Pattern observation: The number of operations grows directly with the number of items.
Final Time Complexity
Time Complexity: O(n)
This means the time grows in a straight line as the list gets bigger.
Common Mistake
[X] Wrong: "lapply and sapply run faster because they are special functions."
[OK] Correct: They still apply the function to each item one by one, so time grows with the number of items.
Interview Connect
Understanding how these functions scale helps you write efficient code and explain your choices clearly in real projects.
Self-Check
"What if the function inside lapply took longer for bigger numbers? How would the time complexity change?"