WEEK 3 Time Complexity and Asymptotic Notation

Algorithms and their Applications CS2004 (2024-2025)

3.1 Time Complexity and Asymptotic Notation

Dr. Mahir Arzoky

Page 1: Introduction

• Overview of the lecture on Time Complexity and Asymptotic Notation.

Page 2: Previous Topics

• Concepts covered so far:

  • Concepts of Computation and Algorithms

  • Comparing algorithms

  • Asymptotic Analysis

  • Mathematical foundations (available on Brightspace)

Page 3: Lecture Focus

• Topics to be discussed:

  • Selection Sort algorithm

  • Binary Search algorithm

  • Big-Oh notation

  • Classes of algorithms

Page 4: Sorting

• Importance of sorting in data analysis:

  • Examples include sorting employees by salary and names alphabetically.

• Overview of sorting algorithms:

  • Selection Sort: finds the smallest element in the unsorted portion and moves it to the front.

Page 5-7: Selection Sort Algorithm

• Part 1: Sorting an array of integers.

  • Original array: 11, 9, 17, 5, 12

  • Find the smallest and swap with the first element.

• Part 2: Continue finding the next smallest.

  • Example progression: 5, 9, 17, 11, 12 → 5, 9, 11, 17, 12

• Part 3: Repeat until the unsorted portion is of length 1.

Page 8: Time Complexity of Selection Sort

• Count of primitive operations for an array of size n:

  • Finding the smallest requires visiting n elements + 2 for the swap.

  • Total operations: O(n²) using Big-Oh notation.

Page 9: Search Algorithms

• Types of searching algorithms:

  • Sequential Search: checks each element, does not require sorted data.

  • Interval Search (Binary Search): requires sorted data and uses a divide and conquer approach.

Page 10-11: Binary Search Example

• Task: Search for a key in a sorted list.

• Process:

  • Check the middle element.

  • If the key is less than the middle, search the first half; otherwise, search the second half.

• Repeat until the key is found or confirmed absent.

Page 12: Binary Search vs. Linear Search

• Binary Search: O(log₂(n))

• Linear Search: O(n)

• Conclusion: Binary search is faster but only works on sorted data.

Page 13: Performance Comparison

• Example with a million unsorted elements:

  • Linear search: O(n)

  • Binary search + Selection sort: O(n²)

  • Conclusion: Linear search is faster in this scenario.

Page 14: Importance of Algorithm Runtime Definition

• Need to define runtime without experimental studies due to varying factors (processor speed, etc.).

• Algorithmic complexity indicates performance.

Page 15: Asymptotic Algorithm Analysis

• Determines running time in Big-Oh notation.

• Focus on worst-case number of primitive operations as a function of input size.

Page 16: Steps for Big-Oh Runtime Analysis

1. Identify input and what n represents.

2. Calculate primitive operations in terms of n.

3. Drop lower-order terms.

4. Remove constant factors.

Page 17: Example of Asymptotic Analysis

• Example: ArrayMax algorithm with T(n) = 8n - 5.

• Result: Runs in O(n) time.

Page 19: Ranking Algorithms from Fast to Slow

• Rankings based on time complexity:

  1. O(log n)

  2. O(n)

  3. O(n log n)

  4. O(n²)

  5. O(n² log n)

  6. O(n⁴)

  7. O(2ⁿ)

Page 20: Computational Complexity

• Algorithms with O(2ⁿ) complexity are inefficient.

• Questioning the existence of better polynomial time algorithms.

Page 21: Polynomial Time Definition

• An algorithm is solvable in polynomial time if it requires O(n^k) steps for some non-negative integer k.

Page 22-24: Classes of Algorithms

• Computable: Problems solvable by a computer (e.g., f(x) = x + 1).

• Non-Computable: Problems that cannot be solved (e.g., Halting Problem).

• P Problems: Solvable in polynomial time (e.g., multiplication, sorting).

• NP Problems: Difficult to solve but easy to verify (e.g., job scheduling).

• NP-HARD: Very difficult problems, not solvable in polynomial time.

• NP-COMPLETE: Hardest problems in NP, no known polynomial-time solutions.

Page 25-26: Implications of NP-COMPLETE

• Finding a polynomial-time algorithm for any NP-COMPLETE problem would imply all NP problems can be solved in polynomial time.

Page 27: Examples of NP-Complete Problems

• Travelling salesperson problem

• Finding the shortest common superstring

• Checking language acceptance of finite automata

Page 28-29: P vs NP Question

• Essence: If checking a solution is easy, is solving the problem also easy?

• Consequences of proving P=NP could lead to security vulnerabilities.

Page 30: Next Topics

• Upcoming lecture on data structures and their applications.

• Laboratory work on implementing and comparing algorithms, computing T(n) and O(n), and running experiments.