Named vectors in R Programming - Time & Space Complexity

Time Complexity: Named vectors

O(n)

Understanding Time Complexity

We want to understand how the time it takes to work with named vectors changes as the vector gets bigger.

Specifically, how does looking up or accessing elements by name affect the time?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

  
# Create a named vector
vec <- c(a=10, b=20, c=30, d=40, e=50)

# Access element by name
value <- vec["c"]

# Access multiple elements by names
values <- vec[c("a", "e")]

# Add a new named element
vec["f"] <- 60

This code creates a named vector, accesses elements by their names, and adds a new named element.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Searching for names in the vector's name list to find matching elements.
• How many times: Once per element accessed by name; if multiple names are accessed, the search repeats for each.

How Execution Grows With Input

When the vector is small, finding a name is quick. As the vector grows, searching through names takes longer.

Input Size (n)	Approx. Operations
10	About 10 checks to find a name
100	About 100 checks to find a name
1000	About 1000 checks to find a name

Pattern observation: The time to find a name grows roughly in direct proportion to the vector size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find an element by name grows linearly with the number of elements in the vector.

Common Mistake

[X] Wrong: "Accessing elements by name is instant no matter how big the vector is."

[OK] Correct: The program must look through the names to find a match, so bigger vectors take more time.

Interview Connect

Understanding how named vectors work helps you reason about data lookup speed, a key skill in many programming tasks.

Self-Check

"What if we changed the vector to a named list instead? How would the time complexity for accessing elements by name change?"