Time Complexity: SLA misses and notifications
O(n)
0
0
SLA misses and notifications in Apache Airflow - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes to check SLA misses and send notifications grows as the number of tasks increases.
How does the system handle more tasks and their SLA checks over time?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
def sla_miss_callback(dag, task_list, blocking_task_list, slas, blocking_tis):
for sla in slas:
send_notification(sla.task_id, sla.execution_date)
# Airflow calls this function when SLA misses happen
# slas is a list of SLA miss objects
# send_notification sends an alert for each SLA miss
This code sends notifications for each SLA miss detected in a DAG run.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Looping over the list of SLA misses.
- How many times: Once for each SLA miss in the list.
How Execution Grows With Input
Each SLA miss causes one notification to be sent, so the work grows directly with the number of SLA misses.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 notifications sent |
| 100 | 100 notifications sent |
| 1000 | 1000 notifications sent |
Pattern observation: The number of notifications grows linearly as SLA misses increase.
Final Time Complexity
Time Complexity: O(n)
This means the time to send notifications grows directly in proportion to the number of SLA misses.
Common Mistake
[X] Wrong: "Sending notifications happens instantly no matter how many SLA misses there are."
[OK] Correct: Each notification takes some time, so more SLA misses mean more notifications and more total time.
Interview Connect
Understanding how notification time grows helps you design systems that handle alerts efficiently as workloads grow.
Self-Check
"What if notifications were sent in batches instead of one by one? How would the time complexity change?"