Time Complexity: Factor creation
O(n)
0
0
Factor creation in R Programming - Time & Space Complexity
Understanding Time Complexity
We want to see how the time needed to create a factor changes as the input grows.
How does making a factor from a vector take more or less time when the vector gets bigger?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
# Create a factor from a character vector
vec <- rep(c("apple", "banana", "cherry"), length.out = n)
fact <- factor(vec)
This code makes a factor from a vector that repeats three fruit names many times.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Scanning the entire vector to assign levels and codes.
- How many times: Once for each element in the vector (n times).
How Execution Grows With Input
As the vector gets longer, the time to create the factor grows roughly in direct proportion.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 scans |
| 100 | About 100 scans |
| 1000 | About 1000 scans |
Pattern observation: Doubling the input roughly doubles the work needed.
Final Time Complexity
Time Complexity: O(n)
This means the time to create a factor grows linearly with the size of the input vector.
Common Mistake
[X] Wrong: "Creating a factor is instant no matter how big the vector is."
[OK] Correct: The function must look at each element to assign levels, so bigger vectors take more time.
Interview Connect
Understanding how factor creation scales helps you reason about data processing speed in R, a useful skill in many coding tasks.
Self-Check
"What if we created a factor from a vector with many unique values instead of just three? How would the time complexity change?"