Directory services (Active Directory, LDAP) in Cybersecurity - Time & Space Complexity

Time Complexity: Directory services (Active Directory, LDAP)

O(n)

Understanding Time Complexity

When working with directory services like Active Directory or LDAP, it is important to understand how the time to find or update information changes as the directory grows.

We want to know how the number of steps needed to search or modify entries changes when there are more users or devices in the directory.

Scenario Under Consideration

Analyze the time complexity of the following LDAP search operation.

ldap_search(connection, base_dn, filter) {
  results = []
  for entry in directory_tree:
    if entry.matches(filter):
      results.append(entry)
  return results
}
    

This code searches through the directory tree to find all entries matching a filter.

Identify Repeating Operations

• Primary operation: Looping through each entry in the directory tree to check if it matches the filter.
• How many times: Once for every entry in the directory, which grows as the directory gets larger.

How Execution Grows With Input

As the number of entries in the directory increases, the search checks more entries 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 number of entries. Double the entries, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the search grows in a straight line as the directory gets bigger.

Common Mistake

[X] Wrong: "Searching a directory is always instant no matter how big it is."

[OK] Correct: The search must check entries one by one unless special indexes or structures are used, so bigger directories take more time.

Interview Connect

Understanding how directory searches scale helps you explain system performance and design better queries in real work situations.

Self-Check

"What if the directory used an index to find entries instead of checking each one? How would the time complexity change?"