Sample Space and Events

4.1. Sample Space. Events

• A random experiment is one that can yield different results even when performed under the same conditions.
  • Examples include tossing a coin or die and drawing a card from a deck.
• A sample space is the set of all possible outcomes of a random experiment, denoted by $E$.
  • For a coin toss, $ E = {H, T} $.
  • For a die roll, $ E = {1, 2, 3, 4, 5, 6} $.
• A random event is a subset of the sample space.
  • Rolling a die and getting an even number: $ {2, 4, 6} $.
  • Tossing a coin twice and getting heads on the first toss: $ {(H, H), (H, T)} $.

Types of Events

• Elementary Event: Each individual element of the sample space.
• Compound Event: Any non-empty subset of the sample space that is not an elementary event.
• Sure Event: The entire sample space $E$, which always occurs.
• Impossible Event: The empty set $\emptyset$, which never occurs.

Operations with Events

• Union of Events ($A \cup B$): Occurs when either $A$ or $B$ occurs.
• Intersection of Events ($A \cap B$): Occurs when both $A$ and $B$ occur simultaneously.
• Complementary Event ($\bar{A}$): Occurs when $A$ does not occur.
• Incompatible Events: Two events $A$ and $B$ that cannot occur at the same time, i.e., $A \cap B = \emptyset$.

4.2. Probability of an Event

• The probability of an event $A$, denoted as $P(A)$, is a number between 0 and 1 indicating the likelihood of the event occurring.

Calculation of Probabilities

• Laplace's Rule: If all elementary events in the sample space are equally likely, then: $$ P(A) = \frac{\text{Number of favorable outcomes for A}}{\text{Number of possible outcomes}} $$
• Frequentist Probability: After repeating a random experiment a large number of times, the probability of an event $A$ approaches the relative frequency with which $A$ occurs.

Properties of Probability

• $P(E) = 1$
• $P(\emptyset) = 0$
• $0 \le P(A) \le 1$
• $P(\bar{A}) = 1 - P(A)$
• $P(A \cup B) = P(A) + P(B) - P(A \cap B)$
• If $A$ and $B$ are incompatible: $P(A \cup B) = P(A) + P(B)$

4.3. Conditional Probability

• The conditional probability of an event $A$ given that event $B$ has occurred, denoted as $P(A/B)$, is the probability of $A$ occurring given that $B$ has occurred. $$ P(A/B) = \frac{P(A \cap B)}{P(B)} $$

Dependent and Independent Events

• Two events $A$ and $B$ are independent if the occurrence of one does not affect the occurrence of the other.
  • $P(A/B) = P(A)$
  • $P(B/A) = P(B)$
  • $P(A \cap B) = P(A) \cdot P(B)$
• Two events $A$ and $B$ are dependent if the occurrence of one affects the occurrence of the other.
  • $P(A \cap B) = P(A) \cdot P(B/A)$
  • $P(A \cap B) = P(B) \cdot P(A/B)$

Theorem of Total Probability

• If $A_1, A_2,..., A_n$ are pairwise incompatible events such that $A_1 \cup A_2 \cup... \cup A_n = E$, then for any event $B$: $$ P(B) = P(A_1) \cdot P(B/A_1) + P(A_2) \cdot P(B/A_2) +... + P(A_n) \cdot P(B/A_n) $$

Bayes' Theorem

• If $A_1, A_2,..., A_n$ are pairwise incompatible events such that $A_1 \cup A_2 \cup... \cup A_n = E$, then for any event $B$: $$ P(A_i/B) = \frac{P(A_i) \cdot P(B/A_i)}{P(B)} $$ where $P(B)$ is calculated using the theorem of total probability.

Algorithmic Complexity

• Algorithmic complexity measures the time (time complexity) or memory (space complexity) an algorithm needs for a given input size.
• Big O notation expresses it.
• Focuses on growth as input size increases (asymptotic behavior).
• Compares algorithm efficiency for task optimization.

Types of Complexity

• Time Complexity: Time taken by an algorithm as a function of input length.
• Space Complexity: Memory space required by an algorithm as a function of input length.
  • Includes space for input data and auxiliary variables.

Big O Notation

• Mathematical notation describing function behavior as argument approaches a value or infinity.
• Classifies algorithms by how their time or space grows with input size.
• Provides an upper bound on growth rate.

Common Complexities

• $O(1)$: Constant, e.g., accessing an array element.
• $O(\log n)$: Logarithmic, e.g., binary search.
• $O(n)$: Linear, e.g., searching an unsorted array.
• $O(n \log n)$: Log-linear, e.g., merge sort, quicksort (average case).
• $O(n^2)$: Quadratic, e.g., bubble sort, insertion sort.
• $O(2^n)$: Exponential, e.g., Tower of Hanoi.
• $O(n!)$: Factorial, e.g., generating all permutations.

How to Determine Complexity

• Identify input size ($n$).
• Count elementary operations (addition, assignment, comparisons).
• Express operations as a function of $n$.
• Simplify using Big O rules.
  • Drop constants: $O(2n) \rightarrow O(n)$.
  • Keep dominant term: $O(n^2 + n) \rightarrow O(n^2)$.

Example: Summing an Array

def sum_array(arr):
    sum = 0 # O(1)
    for num in arr: # O(n)
        sum += num # O(1)
    return sum # O(1)

• Loop runs $n$ times, where $n$ is the array size.
• Operations inside the loop take constant time.
• Total time complexity: $O(n)$.

Practical Implications

• Right algorithm choice impacts performance, especially for large datasets.
• Complexity helps predict algorithm scaling.
• Guides decisions in software design and optimization.
• Real-world performance affected by factors not in Big O (hardware, language).

Common Data Structure Operations

Tips

• Always consider worst-case complexity.
• Be aware of space-time trade-offs.
• Use profiling tools to measure actual performance.
• Understand Big O limitations; it's a valuable but incomplete analysis tool.