KR

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.