Algorithms and Complexity

Complexity Theory and Big O Notation

• Edmund Landau:
  • German mathematician
  • Famous for contributions to number theory and complex analysis
  • Proposed four unsolved problems known as Landau's problems in 1912
• Big O Notation:
  • Introduced by Edmund Landau
  • Used to compare the growth of different functions
  • Describes the upper bound of an algorithm's time or space complexity
  • Defines the growth rate of an algorithm as the input size increases
• Definitions:
  • f(n) ∈ O(g(n)) if there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
  • f(n) ∈ o(g(n)) if f(n) grows slower than g(n) as n approaches infinity
  • f(n) ∈ Ω(g(n)) if f(n) grows as fast as g(n) as n approaches infinity
  • f(n) ∈ Θ(g(n)) if f(n) grows at the same rate as g(n) as n approaches infinity
• Rules of Big O Notation:
  • Constant factors do not change the growth rate
  • Summing two functions of the same class preserves the complexity class
  • The product of two functions of the same class preserves the complexity class
  • Transitive property: if f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)), then f(n) ∈ O(h(n))

Complexity Classes

• Time Complexity:
  • Defines the growth rate of an algorithm's computation time as the input size increases
  • Measured using Big O notation
• Space Complexity:
  • Defines the growth rate of an algorithm's memory usage as the input size increases
  • Measured using Big O notation
• Complexity Classes:
  • TIME(f(n)) and SPACE(f(n)) define the complexity class of an algorithm
  • TIME(f(n)) ⊆ SPACE(f(n)) for every function f(n)

Sorting Algorithms

• Selection Sort:
  • Basic sorting algorithm with time complexity Θ(n^2)
  • Space complexity is Θ(n) since there is no additional space requirement
• Other Sorting Algorithms:
  • BubbleSort: time complexity Θ(n^2), space complexity Θ(n)
  • HeapSort: time complexity Θ(n log n), space complexity Θ(n)
  • MergeSort: time complexity Θ(n log n), space complexity Θ(n)
  • QuickSort: time complexity Θ(n log n), space complexity Θ(n)

Lower Bounds and NP-Completeness

• Lower Bounds:
  • Ω(n log n) is a lower bound for the time complexity of comparison-based sorting algorithms
  • Any comparison-based sorting algorithm will require at least Ω(n log n) computational steps
• P=NP?:
  • One of the most important open questions in computer science
  • Relates to the complexity classes P (polynomial time) and NP (nondeterministic polynomial time)
  • P=NP? asks if every problem whose solution can be efficiently verified can also be efficiently solved### Complexity Theory
• The complexity class PTIME (also DTIME or P) is the class of all problems and algorithms with a runtime of order O(p(n)) for an arbitrary polynomial p(n).
• The complexity class PSPACE (also DSPACE) is the class of all problems and algorithms with a space complexity of order O(p(n)) for an arbitrary polynomial p(n).
• The complexity class EXPTIME, often abbreviated to EXP, is the class of all problems and algorithms with a runtime of order O(2^n) for an arbitrary natural number k ∈ ℕ.
• The complexity class EXPSPACE is the class of all problems and algorithms with a space complexity of order O(2^n) for an arbitrary natural number k ∈ ℕ.

Non-Deterministic Turing Machines

• Non-deterministic Turing machines do not have to systematically try out different possible solutions for the respective problem.
• They guess the (or a) correct solution, if one exists, and then check whether it is correct.
• Non-deterministic Turing machines can potentially solve certain problems faster than a deterministic Turing machine.

Complexity Classes for Non-Deterministic Turing Machines

• The complexity class NTIME, often abbreviated as NP, is the class of all problems and algorithms with a runtime of order O(p(n)) for an arbitrary polynomial p(n) on a non-deterministic Turing machine.
• The complexity class NSPACE is the class of all problems and algorithms with a space complexity of order O(p(n)) for an arbitrary polynomial p(n) on a non-deterministic Turing machine.

Relationships Between Complexity Classes

• P ⊆ NP ⊆ PSPACE = NSPACE ⊆ EXP
• The first subset relationship is clear since a deterministic Turing machine is a special case of a non-deterministic Turing machine.
• The third subset relationship NSPACE⊆EXP follows from the relation SPACE(h(n)) ⊆ TIME(O(h(n) · 2^h(n)))

NP-Completeness

• A language LNP is NP-hard if all languages L ∈ NP can be polynomially reduced to LNP.
• A language LNP is NP-complete if it is NP-hard and it lies in NP.
• NP-complete languages are the hardest ones in NP, because every other language can be polynomially reduced to such a language.

Theorems

• If it can be shown that an NP-complete language is in P, then all NP-complete languages are in P and it holds that P = NP.
• If it can be shown that an NP-complete language is not in P, then all NP-complete languages are not in P and it holds that P ≠ NP.

Cook's Theorem

• The satisfiability problem of propositional logic, i.e., the SAT problem, is NP-complete.

Quantum Computers

• The set of functions computable on a quantum computer coincides with the set of functions computable on a Turing machine.
• However, since quantum computers function in a significantly different way, the complexity of functions can be very different in certain cases.
• Quantum computers work with QBits instead of classical bits.
• Quantum computers can, to a certain extent, carry out calculations for different values in one step in order to then only consider those values for which the computation was successful.

BQP

• BQP stands for "bounded error, quantum, polynomial time."
• This complexity class contains functions that can be computed in polynomial time on a quantum computer.
• Bounded error refers to the fact that calculations on a quantum computer have a certain error probability that must be sufficiently small.

Algorithms in BQP

• The Shor algorithm enables prime factorization in polynomial time.
• Another of Shor's algorithms calculates discrete logarithms in polynomial time.
• The Grover algorithm is used to search in an unsorted list.

Complexity Theory and Big O Notation

• Edmund Landau:
  • German mathematician
  • Famous for contributions to number theory and complex analysis
  • Proposed four unsolved problems known as Landau's problems in 1912
• Big O Notation:
  • Introduced by Edmund Landau
  • Used to compare the growth of different functions
  • Describes the upper bound of an algorithm's time or space complexity
  • Defines the growth rate of an algorithm as the input size increases
• Definitions:
  • f(n) ∈ O(g(n)) if there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
  • f(n) ∈ o(g(n)) if f(n) grows slower than g(n) as n approaches infinity
  • f(n) ∈ Ω(g(n)) if f(n) grows as fast as g(n) as n approaches infinity
  • f(n) ∈ Θ(g(n)) if f(n) grows at the same rate as g(n) as n approaches infinity
• Rules of Big O Notation:
  • Constant factors do not change the growth rate
  • Summing two functions of the same class preserves the complexity class
  • The product of two functions of the same class preserves the complexity class
  • Transitive property: if f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)), then f(n) ∈ O(h(n))

Complexity Classes

• Time Complexity:
  • Defines the growth rate of an algorithm's computation time as the input size increases
  • Measured using Big O notation
• Space Complexity:
  • Defines the growth rate of an algorithm's memory usage as the input size increases
  • Measured using Big O notation
• Complexity Classes:
  • TIME(f(n)) and SPACE(f(n)) define the complexity class of an algorithm
  • TIME(f(n)) ⊆ SPACE(f(n)) for every function f(n)

Sorting Algorithms

• Selection Sort:
  • Basic sorting algorithm with time complexity Θ(n^2)
  • Space complexity is Θ(n) since there is no additional space requirement
• Other Sorting Algorithms:
  • BubbleSort: time complexity Θ(n^2), space complexity Θ(n)
  • HeapSort: time complexity Θ(n log n), space complexity Θ(n)
  • MergeSort: time complexity Θ(n log n), space complexity Θ(n)
  • QuickSort: time complexity Θ(n log n), space complexity Θ(n)

Lower Bounds and NP-Completeness

• Lower Bounds:
  • Ω(n log n) is a lower bound for the time complexity of comparison-based sorting algorithms
  • Any comparison-based sorting algorithm will require at least Ω(n log n) computational steps
• P=NP?:
  • One of the most important open questions in computer science
  • Relates to the complexity classes P (polynomial time) and NP (nondeterministic polynomial time)
  • P=NP? asks if every problem whose solution can be efficiently verified can also be efficiently solved### Complexity Theory
• The complexity class PTIME (also DTIME or P) is the class of all problems and algorithms with a runtime of order O(p(n)) for an arbitrary polynomial p(n).
• The complexity class PSPACE (also DSPACE) is the class of all problems and algorithms with a space complexity of order O(p(n)) for an arbitrary polynomial p(n).
• The complexity class EXPTIME, often abbreviated to EXP, is the class of all problems and algorithms with a runtime of order O(2^n) for an arbitrary natural number k ∈ ℕ.
• The complexity class EXPSPACE is the class of all problems and algorithms with a space complexity of order O(2^n) for an arbitrary natural number k ∈ ℕ.

Non-Deterministic Turing Machines

• Non-deterministic Turing machines do not have to systematically try out different possible solutions for the respective problem.
• They guess the (or a) correct solution, if one exists, and then check whether it is correct.
• Non-deterministic Turing machines can potentially solve certain problems faster than a deterministic Turing machine.

Complexity Classes for Non-Deterministic Turing Machines

• The complexity class NTIME, often abbreviated as NP, is the class of all problems and algorithms with a runtime of order O(p(n)) for an arbitrary polynomial p(n) on a non-deterministic Turing machine.
• The complexity class NSPACE is the class of all problems and algorithms with a space complexity of order O(p(n)) for an arbitrary polynomial p(n) on a non-deterministic Turing machine.

Relationships Between Complexity Classes

• P ⊆ NP ⊆ PSPACE = NSPACE ⊆ EXP
• The first subset relationship is clear since a deterministic Turing machine is a special case of a non-deterministic Turing machine.
• The third subset relationship NSPACE⊆EXP follows from the relation SPACE(h(n)) ⊆ TIME(O(h(n) · 2^h(n)))

NP-Completeness

• A language LNP is NP-hard if all languages L ∈ NP can be polynomially reduced to LNP.
• A language LNP is NP-complete if it is NP-hard and it lies in NP.
• NP-complete languages are the hardest ones in NP, because every other language can be polynomially reduced to such a language.

Theorems

• If it can be shown that an NP-complete language is in P, then all NP-complete languages are in P and it holds that P = NP.
• If it can be shown that an NP-complete language is not in P, then all NP-complete languages are not in P and it holds that P ≠ NP.

Cook's Theorem

• The satisfiability problem of propositional logic, i.e., the SAT problem, is NP-complete.

Quantum Computers

• The set of functions computable on a quantum computer coincides with the set of functions computable on a Turing machine.
• However, since quantum computers function in a significantly different way, the complexity of functions can be very different in certain cases.
• Quantum computers work with QBits instead of classical bits.
• Quantum computers can, to a certain extent, carry out calculations for different values in one step in order to then only consider those values for which the computation was successful.

BQP

• BQP stands for "bounded error, quantum, polynomial time."
• This complexity class contains functions that can be computed in polynomial time on a quantum computer.
• Bounded error refers to the fact that calculations on a quantum computer have a certain error probability that must be sufficiently small.

Algorithms in BQP

• The Shor algorithm enables prime factorization in polynomial time.
• Another of Shor's algorithms calculates discrete logarithms in polynomial time.
• The Grover algorithm is used to search in an unsorted list.