Time Complexity: Logical indexing
O(n)
0
0
Logical indexing in R Programming - Time & Space Complexity
Understanding Time Complexity
Logical indexing lets us pick elements from a list or vector using true or false values.
We want to see how the time to do this grows as the list gets bigger.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
x <- 1:1000
idx <- x %% 2 == 0
result <- x[idx]This code creates a vector from 1 to 1000, makes a logical vector marking even numbers, and selects those even numbers.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Checking each element to see if it meets the condition (even number).
- How many times: Once for every element in the vector (n times).
How Execution Grows With Input
As the vector gets bigger, the program checks more elements one by one.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks |
| 100 | 100 checks |
| 1000 | 1000 checks |
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 select elements grows in a straight line as the list gets longer.
Common Mistake
[X] Wrong: "Logical indexing is instant no matter how big the vector is."
[OK] Correct: The program must check each element to decide if it matches, so bigger vectors take more time.
Interview Connect
Understanding how logical indexing scales helps you write efficient data filters and shows you can think about code speed clearly.
Self-Check
"What if we used multiple conditions combined with & or | for logical indexing? How would the time complexity change?"