SCARD for set size in Redis - Time & Space Complexity

Time Complexity: SCARD for set size

O(1)

Understanding Time Complexity

We want to understand how the time to get the size of a set in Redis changes as the set grows.

How does the command SCARD perform when the set has more or fewer elements?

Scenario Under Consideration

Analyze the time complexity of the following Redis command.

# Get the number of elements in a set named 'myset'
SCARD myset
    

This command returns the count of items stored in the set 'myset'.

Identify Repeating Operations

SCARD does not loop through the set elements to count them.

• Primary operation: Direct retrieval of the stored size value.
• How many times: Only once per command call.

How Execution Grows With Input

The time to get the set size stays almost the same no matter how many elements are in the set.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The operation count does not increase with the size of the set.

Final Time Complexity

Time Complexity: O(1)

This means the time to get the set size stays constant no matter how big the set is.

Common Mistake

[X] Wrong: "SCARD must check every element to count them, so it gets slower with bigger sets."

[OK] Correct: Redis stores the size of the set internally, so SCARD just reads that number directly without scanning elements.

Interview Connect

Knowing that SCARD runs in constant time shows you understand how Redis optimizes common operations, which is a useful skill for working with fast data stores.

Self-Check

"What if we used a command that lists all set members instead of SCARD? How would the time complexity change?"

Practice

1. What does the Redis command SCARD do when used on a set?

easy

A. Returns all elements in the set

B. Deletes all elements from the set

C. Adds a new element to the set

D. Returns the number of unique elements in the set

Solution

1. Step 1: Understand the purpose of SCARD

   The SCARD command is designed to count elements in a set, not modify or list them.

2. Step 2: Identify the correct behavior

   SCARD returns the count of unique elements stored in the set.

3. Final Answer:

   Returns the number of unique elements in the set -> Option D

4. Quick Check:

   SCARD = set size count [OK]

Hint: SCARD counts set items without listing them [OK]

Common Mistakes:

• Confusing SCARD with commands that list or delete elements
• Thinking SCARD adds elements
• Assuming SCARD returns elements instead of count

2. Which of the following is the correct syntax to get the size of a set named myset in Redis?

easy

A. SCARD myset

B. SCARD(myset)

C. GETSIZE myset

D. SIZE myset

Solution

1. Step 1: Recall Redis command syntax

   Redis commands use the format COMMAND key without parentheses.

2. Step 2: Match correct command for set size

   SCARD is the command to get set size, so SCARD myset is correct.

3. Final Answer:

   SCARD myset -> Option A

4. Quick Check:

   Correct Redis syntax = SCARD myset [OK]

Hint: Redis commands have no parentheses, just command and key [OK]

Common Mistakes:

• Using parentheses like a function call
• Using non-existent commands like GETSIZE or SIZE
• Confusing SCARD with GET

3. Given the following Redis commands executed in order:

SADD fruits apple banana orange
SADD fruits banana grape
SCARD fruits

What will be the output of SCARD fruits?

medium

A. 3

B. 5

C. 4

D. 2

Solution

1. Step 1: Identify unique elements added to the set

   First SADD adds apple, banana, orange (3 unique). Second SADD adds banana (already exists), grape (new).

2. Step 2: Count unique elements after both commands

   Unique elements are apple, banana, orange, grape = 4 total.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Unique fruits count = 4 [OK]

Hint: SCARD counts unique items, duplicates ignored [OK]

Common Mistakes:

• Counting duplicates multiple times
• Assuming SADD overwrites set
• Confusing SCARD output with list of elements

4. You run the command SCARD myset but get an error: WRONGTYPE Operation against a key holding the wrong kind of value. What is the most likely cause?

medium

A. myset is not a set but another data type like string or list

B. The key myset does not exist

C. SCARD command is misspelled

D. Redis server is down

Solution

1. Step 1: Understand the error message

   The error indicates the key exists but is not a set type.

2. Step 2: Identify cause of WRONGTYPE error

   SCARD only works on sets; if myset is string or list, this error occurs.

3. Final Answer:

   myset is not a set but another data type like string or list -> Option A

4. Quick Check:

   WRONGTYPE = wrong data type for SCARD [OK]

Hint: WRONGTYPE means key is not a set [OK]

Common Mistakes:

• Assuming key does not exist causes this error
• Thinking SCARD command spelling causes this error
• Ignoring data type mismatch

5. You have two sets in Redis: setA with 3 elements and setB with 4 elements, where 2 elements overlap. You want to find the total number of unique elements across both sets without retrieving all elements. Which Redis command or combination should you use?

hard

A. SCARD setA + SCARD setB

B. SUNIONSTORE tempSet setA setB followed by SCARD tempSet

C. SINTER setA setB

D. SDIFF setA setB

Solution

1. Step 1: Understand the problem of counting unique elements across two sets

   Simply adding SCARD results counts duplicates twice.

2. Step 2: Use SUNIONSTORE to combine sets uniquely

   SUNIONSTORE creates a new set with all unique elements from both sets.

3. Step 3: Use SCARD on the combined set

   SCARD on the new set gives total unique elements count.

4. Final Answer:

   SUNIONSTORE tempSet setA setB followed by SCARD tempSet -> Option B

5. Quick Check:

   Use SUNIONSTORE + SCARD for unique combined count [OK]

Hint: Combine sets with SUNIONSTORE, then SCARD the result [OK]

Common Mistakes:

• Adding SCARD counts directly causing duplicates
• Using SINTER or SDIFF which don't give total unique count
• Trying to count without combining sets