Deepfakes and misinformation in AI for Everyone - Time & Space Complexity

Time Complexity: Deepfakes and misinformation

O(n * m)

Understanding Time Complexity

We want to understand how the effort to create or detect deepfakes changes as the amount of data grows.

How does the time needed grow when more videos or images are involved?

Scenario Under Consideration

Analyze the time complexity of the following simplified deepfake detection process.

for each video in videos:
    for each frame in video:
        analyze frame for deepfake signs
    combine frame results for video decision

This code checks every frame in every video to decide if the video is a deepfake.

Identify Repeating Operations

Look at what repeats most in this process.

• Primary operation: Analyzing each frame for deepfake signs.
• How many times: Once for every frame in every video.

How Execution Grows With Input

As the number of videos or frames grows, the total work grows too.

Input Size (videos x frames)	Approx. Operations
10 videos x 30 frames	300 analyses
100 videos x 30 frames	3,000 analyses
1,000 videos x 30 frames	30,000 analyses

Pattern observation: The work grows directly with the total number of frames checked.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the number of videos (n) times the number of frames per video (m).

Common Mistake

[X] Wrong: "Checking one frame means the whole video is checked instantly."

[OK] Correct: Each frame needs separate analysis, so time adds up with more frames.

Interview Connect

Understanding how work grows with data size helps you explain system limits and design better solutions.

Self-Check

What if we only analyzed every other frame instead of all frames? How would the time complexity change?

Practice

1. What is a deepfake?

easy

A. A software update

B. A type of computer virus

C. A fake video or image made by AI that looks real

D. A real news report

Solution

1. Step 1: Understand the definition of deepfake

   A deepfake is created using AI to make fake videos or images that look real.

2. Step 2: Compare options with the definition

   Only a fake video or image made by AI that looks real matches this definition exactly.

3. Final Answer:

   A fake video or image made by AI that looks real -> Option C

4. Quick Check:

   Deepfake = Fake AI video/image [OK]

Hint: Deepfake means fake AI-made video or image [OK]

Common Mistakes:

• Confusing deepfake with virus
• Thinking deepfake is real news
• Mixing deepfake with software updates

2. Which of these is a common way to spot a deepfake?

easy

A. Check for unusual blinking or facial movements

B. Look for spelling mistakes in the video

C. Check the video length

D. See if the video is in black and white

Solution

1. Step 1: Identify signs of deepfakes

   Deepfakes often have unnatural blinking or strange facial movements because AI struggles with these details.

2. Step 2: Evaluate options

   Only Check for unusual blinking or facial movements describes a known sign of deepfakes; others are unrelated.

3. Final Answer:

   Check for unusual blinking or facial movements -> Option A

4. Quick Check:

   Unnatural blinking = Deepfake clue [OK]

Hint: Look for weird blinking or face moves [OK]

Common Mistakes:

• Thinking spelling mistakes appear in videos
• Checking video length as a clue
• Assuming black and white means fake

3. If a deepfake video shows a politician saying something shocking, what should you do first?

medium

A. Check trusted news sources to verify

B. Share it immediately on social media

C. Ignore it completely

D. Assume it is true because it looks real

Solution

1. Step 1: Understand the risk of misinformation

   Deepfakes can spread false information, so verifying facts is important.

2. Step 2: Choose the best action

   Checking trusted news sources helps confirm if the video is real or fake.

3. Final Answer:

   Check trusted news sources to verify -> Option A

4. Quick Check:

   Verify before sharing = Check trusted news sources to verify [OK]

Hint: Always verify shocking videos with trusted news [OK]

Common Mistakes:

• Sharing without checking
• Ignoring important info
• Assuming video truth from appearance

4. A video looks real but has strange lighting and mismatched shadows. What is likely the problem?

medium

A. The video is corrupted

B. It is a deepfake with editing errors

C. The camera lens is dirty

D. The video is in slow motion

Solution

1. Step 1: Analyze visual clues in the video

   Strange lighting and mismatched shadows often happen in deepfakes due to AI editing limits.

2. Step 2: Match clues to options

   It is a deepfake with editing errors explains these signs as deepfake editing errors; others do not fit the symptoms.

3. Final Answer:

   It is a deepfake with editing errors -> Option B

4. Quick Check:

   Lighting/shadow errors = Deepfake sign [OK]

Hint: Odd shadows often mean deepfake editing errors [OK]

Common Mistakes:

• Thinking video corruption causes shadows
• Blaming dirty lens for lighting
• Confusing slow motion with lighting issues

5. You receive a video showing a celebrity endorsing a product, but you suspect it is a deepfake. What is the best way to confirm its authenticity?

hard

A. Share the video to see public reaction

B. Trust the video because it looks professional

C. Ask friends if they believe the video

D. Search for official statements or videos from the celebrity

Solution

1. Step 1: Understand how to verify suspicious videos

   Checking official sources or statements is the most reliable way to confirm if a video is real.

2. Step 2: Evaluate options for confirming authenticity

   Search for official statements or videos from the celebrity uses trusted official info; others rely on appearance or opinions, which can be misleading.

3. Final Answer:

   Search for official statements or videos from the celebrity -> Option D

4. Quick Check:

   Official sources confirm authenticity [OK]

Hint: Verify with official celebrity sources first [OK]

Common Mistakes:

• Trusting video quality alone
• Relying on friends' opinions
• Sharing before verifying