Certificate-based authentication in IOT Protocols - Time & Space Complexity

Time Complexity: Certificate-based authentication

O(n)

Understanding Time Complexity

We want to understand how the time needed to verify certificates grows as more devices connect.

How does the system handle more certificates without slowing down too much?

Scenario Under Consideration

Analyze the time complexity of the following certificate verification process.

function verifyCertificate(deviceCert, trustedCerts) {
  for (let cert of trustedCerts) {
    if (deviceCert.issuer === cert.issuer && deviceCert.signature === cert.signature) {
      return true;
    }
  }
  return false;
}
    

This code checks if a device's certificate matches any trusted certificate by comparing issuer and signature.

Identify Repeating Operations

• Primary operation: Loop through the list of trusted certificates.
• How many times: Once for each trusted certificate until a match is found or list ends.

How Execution Grows With Input

As the number of trusted certificates grows, the time to check increases roughly in a straight line.

Input Size (n)	Approx. Operations
10	Up to 10 comparisons
100	Up to 100 comparisons
1000	Up to 1000 comparisons

Pattern observation: Doubling the trusted certificates roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to verify grows directly with the number of trusted certificates.

Common Mistake

[X] Wrong: "Verification time stays the same no matter how many certificates there are."

[OK] Correct: Each certificate must be checked until a match is found, so more certificates mean more checks.

Interview Connect

Understanding how verification time grows helps you design systems that stay fast as they scale.

Self-Check

"What if trusted certificates were stored in a hash map instead of a list? How would the time complexity change?"