DAG concept (Directed Acyclic Graph) in Apache Airflow - Time & Space Complexity

Time Complexity: DAG concept (Directed Acyclic Graph)

O(n)

Understanding Time Complexity

When working with Airflow, DAGs organize tasks in a flow that never loops back. Understanding how the number of tasks affects execution helps us see how the system scales.

We want to know how the time to process tasks grows as we add more tasks to the DAG.

Scenario Under Consideration

Analyze the time complexity of this simple DAG definition.

from airflow import DAG
from airflow.operators.dummy import DummyOperator
from datetime import datetime

dag = DAG('example_dag', start_date=datetime(2024, 1, 1))

start = DummyOperator(task_id='start', dag=dag)
end = DummyOperator(task_id='end', dag=dag)

for i in range(n):
    task = DummyOperator(task_id=f'task_{i}', dag=dag)
    start >> task >> end

This code creates a DAG with one start task, one end task, and n tasks in between, each connected in parallel between start and end.

Identify Repeating Operations

Look at what repeats as n grows.

• Primary operation: Creating and linking n tasks in a loop.
• How many times: The loop runs n times, once for each task.

How Execution Grows With Input

As you add more tasks, the number of operations grows directly with n.

Input Size (n)	Approx. Operations
10	About 10 task creations and connections
100	About 100 task creations and connections
1000	About 1000 task creations and connections

Pattern observation: The work grows evenly as you add more tasks, doubling tasks roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to build and link tasks grows in a straight line with the number of tasks.

Common Mistake

[X] Wrong: "Adding more tasks will cause the DAG to slow down exponentially because of complex dependencies."

[OK] Correct: In this simple DAG, tasks are connected in parallel, so each new task adds a fixed amount of work, not an exponential increase.

Interview Connect

Understanding how DAG size affects execution helps you design workflows that scale well and avoid bottlenecks. This skill shows you can think about system growth clearly.

Self-Check

What if the tasks were connected in a chain instead of parallel? How would the time complexity change?

Practice

1. What is a DAG in Apache Airflow?

easy

A. A tool to store data in a database

B. A programming language for writing tasks

C. A type of server used to run Airflow

D. A Directed Acyclic Graph that defines task order without loops

Solution

1. Step 1: Understand the meaning of DAG

   DAG stands for Directed Acyclic Graph, which means tasks are connected in one direction without cycles or loops.

2. Step 2: Relate DAG to Airflow

   In Airflow, DAGs organize tasks so they run in a specific order safely and predictably.

3. Final Answer:

   A Directed Acyclic Graph that defines task order without loops -> Option D

4. Quick Check:

   DAG = Directed Acyclic Graph [OK]

Hint: Remember DAG means tasks flow one way, no loops [OK]

Common Mistakes:

• Thinking DAG is a database or server
• Confusing DAG with a programming language
• Assuming tasks can loop back in DAG

2. Which of the following is the correct way to define a DAG in Airflow using Python?

easy

A. dag = DAG('my_dag', schedule_interval='@daily')

B. dag = DAG('my_dag', run_every='daily')

C. dag = DAG('my_dag', interval='daily')

D. dag = DAG('my_dag', schedule='daily')

Solution

1. Step 1: Recall Airflow DAG parameters

   The correct parameter to set the schedule is schedule_interval.

2. Step 2: Match the correct syntax

   Only dag = DAG('my_dag', schedule_interval='@daily') uses schedule_interval='@daily', which is valid syntax.

3. Final Answer:

   dag = DAG('my_dag', schedule_interval='@daily') -> Option A

4. Quick Check:

   Use schedule_interval to set DAG schedule [OK]

Hint: Use schedule_interval, not run_every or schedule [OK]

Common Mistakes:

• Using wrong parameter names like run_every
• Forgetting quotes around schedule value
• Using invalid schedule strings

3. Given this DAG snippet, what is the order of task execution?

task1 >> task2 >> task3

medium

A. task3 runs first, then task2, then task1

B. All tasks run at the same time

C. task1 runs first, then task2, then task3

D. task2 runs first, then task1, then task3

Solution

1. Step 1: Understand the '>>' operator in Airflow

   The '>>' operator means 'set downstream', so task1 runs before task2, and task2 before task3.

2. Step 2: Determine execution order

   Tasks run in the order task1, then task2, then task3.

3. Final Answer:

   task1 runs first, then task2, then task3 -> Option C

4. Quick Check:

   task1 >> task2 >> task3 means sequential order [OK]

Hint: Remember '>>' means run left task before right task [OK]

Common Mistakes:

• Thinking '>>' means run tasks in parallel
• Reversing the order of tasks
• Assuming tasks run simultaneously

4. What is wrong with this DAG task dependency code?

task1.set_downstream(task2)
task2.set_downstream(task1)

medium

A. It creates a cycle, which is not allowed in DAGs

B. The syntax for set_downstream is incorrect

C. Tasks must be named differently

D. No error, this is valid

Solution

1. Step 1: Analyze the dependencies

   task1 depends on task2, and task2 depends on task1, creating a loop.

2. Step 2: Understand DAG rules

   DAGs cannot have cycles; tasks must not depend on each other circularly.

3. Final Answer:

   It creates a cycle, which is not allowed in DAGs -> Option A

4. Quick Check:

   DAGs must be acyclic, no loops allowed [OK]

Hint: Check for circular dependencies to avoid cycles [OK]

Common Mistakes:

• Ignoring circular dependencies
• Assuming set_downstream syntax is wrong
• Thinking task names cause errors

5. You want to create a DAG where task3 runs only after both task1 and task2 complete. Which code correctly sets this dependency?

hard

A. task3 >> task1
task3 >> task2

B. task1 >> task3
task2 >> task3

C. task1 << task3
task2 << task3

D. task3.set_downstream([task1, task2])

Solution

1. Step 1: Understand dependency direction

   To run task3 after task1 and task2, task1 and task2 must be upstream of task3.

2. Step 2: Check correct syntax

   Using '>>' from task1 and task2 to task3 sets task3 to run after both complete.

3. Final Answer:

   task1 >> task3 task2 >> task3 -> Option B

4. Quick Check:

   Upstream tasks >> downstream task [OK]

Hint: Use 'task1 >> task3' and 'task2 >> task3' for multiple dependencies [OK]

Common Mistakes:

• Reversing dependency arrows
• Using set_downstream incorrectly with lists
• Assuming task3 runs before task1 and task2