Algorithmic Complexity and Big O Notation

• Algorithmic complexity is a measure of the time or space an algorithm needs as input size increases.
• It is expressed using Big O notation, representing the upper bound of the growth rate.

Common Complexities (Fastest to Slowest)

• O(1) Constant: Time/space doesn't depend on input size; example: array element access by index.
• O(log n) Logarithmic: Time/space grows logarithmically with input size; example: binary search.
• O(n) Linear: Time/space grows linearly with input size; example: looping through an array.
• O(n log n) Linearithmic: Combination of linear and logarithmic growth; example: merge sort, quicksort.
• O(n^2) Quadratic: Time/space grows quadratically with input size; example: nested loops.
• O(2^n) Exponential: Time/space grows exponentially with input size; example: trying all combinations.
• O(n!) Factorial: Time/space grows factorially with input size; example: generating all permutations.

Key Points of the Visual Representation

• A graph compares the growth rates of different time complexities.
• The x-axis represents the input size (n), and the y-axis represents time or space required.
• O(1) is a horizontal line, indicating constant time.
• O(log n) is a slowly increasing curve, indicating logarithmic time.
• O(n) is a straight line with a slope of 1, indicating linear time.
• O(n log n) grows faster than linear but slower than quadratic.
• O(n^2) grows quadratically.
• O(2^n) grows exponentially, faster than polynomial functions.
• O(n!) grows factorially, faster than exponential functions.
• The graph shows time/space increase with input size, emphasizing efficient algorithms for large inputs.

Derivadas de Funciones Elementales (Derivatives of Elementary Functions)

• $y = k$ has a derivative of $y' = 0$.
• $y = x$ has a derivative of $y' = 1$.
• $y = x^n$ has a derivative of $y' = nx^{n-1}$.
• $y = a^x$ has a derivative of $y' = a^x \cdot \ln a$.
• $y = e^x$ has a derivative of $y' = e^x$.
• $y = \log_a x$ has a derivative of $y' = \frac{1}{x \ln a}$.
• $y = \ln x$ has a derivative of $y' = \frac{1}{x}$.
• $y = \sin x$ has a derivative of $y' = \cos x$.
• $y = \cos x$ has a derivative of $y' = -\sin x$.
• $y = \tan x$ has a derivative of $y' = \frac{1}{\cos^2 x} = 1 + \tan^2 x$.
• $y = \cot x$ has a derivative of $y' = -\frac{1}{\sin^2 x} = -(1 + \cot^2 x)$.
• $y = \arcsin x$ has a derivative of $y' = \frac{1}{\sqrt{1-x^2}}$.
• $y = \arccos x$ has a derivative of $y' = -\frac{1}{\sqrt{1-x^2}}$.
• $y = \arctan x$ has a derivative of $y' = \frac{1}{1+x^2}$.
• $y = \operatorname{arccot} x$ has a derivative of $y' = -\frac{1}{1+x^2}$.

Reglas de Derivación (Differentiation Rules)

• $y = k \cdot u \Longrightarrow y' = k \cdot u'$, where $k$ is a constant and $u$ is a differentiable function of $x$.
• $y = u \pm v \Longrightarrow y' = u' \pm v'$, where $u$ and $v$ are differentiable functions of $x$.
• $y = u \cdot v \Longrightarrow y' = u' \cdot v + u \cdot v'$, where $u$ and $v$ are differentiable functions of $x$.
• $y = \frac{u}{v} \Longrightarrow y' = \frac{u' \cdot v - u \cdot v'}{v^2}$, where $u$ and $v$ are differentiable functions of $x$.
• $y = f(u) \Longrightarrow y' = f'(u) \cdot u'$ (Chain Rule).

Ejercicios (Exercises)

• $y = 5x^3 - 2x^2 + x - 7 \Longrightarrow y' = 15x^2 - 4x + 1$
• $y = \sqrt{x} \Longrightarrow y' = \frac{1}{2\sqrt{x}}$
• $y = \ln(5x^2 + 3) \Longrightarrow y' = \frac{10x}{5x^2 + 3}$
• $y = \sin(x^2) \Longrightarrow y' = 2x\cos(x^2)$
• $y = e^{\cos x} \Longrightarrow y' = -e^{\cos x} \cdot \sin x$
• $y = \sin x \cdot \cos x \Longrightarrow y' = \cos^2 x - \sin^2 x = \cos(2x)$

Vectores (Vectors)

Suma de vectores (Vector Addition)

• Método gráfico (Graphical method): Place vectors A and B sequentially, maintaining magnitude, direction, and sense; the resultant vector R connects the origin of A to the end of B.
• Método analítico (Analytical method): Use the expressions $R_x = A_x + B_x$, $R_y = A_y + B_y$, $R = \sqrt{R_x^2 + R_y^2}$, and $θ = tan^{-1} (\frac{R_y}{R_x})$.

Producto escalar (Scalar Product/Dot Product)

• $\overrightarrow{A} \cdot \overrightarrow{B} = AB \cos θ = A_x B_x + A_y B_y + A_z B_z$

Producto vectorial (Vector Product/Cross Product)

• $\overrightarrow{A} \times \overrightarrow{B} = AB \sin θ \hat{n}$
• $\overrightarrow{A} \times \overrightarrow{B} = \begin{vmatrix} \hat{i} & \hat{j} & \hat{k} \ A_x & A_y & A_z \ B_x & B_y & B_z \end{vmatrix} = (A_y B_z - A_z B_y)\hat{i} + (A_z B_x - A_x B_z)\hat{j} + (A_x B_y - A_y B_x)\hat{k}$

Cinemática (Kinematics)

MRU (Uniform Rectilinear Motion)

• Equations: $v = \frac{x}{t}$, $x = v \cdot t$

MRUV (Uniformly Accelerated Rectilinear Motion)

• Equations: $v = v_0 + at$, $x = v_0 t + \frac{1}{2} a t^2$, $v^2 = v_0^2 + 2ax$, $x = \frac{v_0 + v}{2} t$

Tiro vertical y caída libre (Vertical Throw and Free Fall)

• Equations: $v = v_0 - gt$, $y = v_0 t - \frac{1}{2} g t^2$, $v^2 = v_0^2 - 2gy$, $y = \frac{v_0 + v}{2} t$

Tiro oblicuo (Oblique Projectile Motion)

• Equations: $v_{0x} = v_0 \cos θ$, $v_{0y} = v_0 \sin θ$, $x = v_{0x} t$, $y = v_{0y} t - \frac{1}{2} g t^2$, $v_y = v_{0y} - gt$, $t_{max} = \frac{v_{0y}}{g}$, $t_{vuelo} = \frac{2v_{0y}}{g}$, $x_{max} = \frac{v_0^2 \sin 2θ}{g}$, $y_{max} = \frac{v_{0y}^2}{2g}$

MCU (Uniform Circular Motion)

• Equations: $ω = \frac{Δθ}{Δt}$, $α = \frac{Δω}{Δt}$, $v = ωr$, $a_c = \frac{v^2}{r} = ω^2 r$, $T = \frac{2π}{ω}$, $f = \frac{1}{T} = \frac{ω}{2π}$

MCUV (Uniformly Accelerated Circular Motion)

• Equations: $ω = ω_0 + αt$, $θ = ω_0 t + \frac{1}{2} α t^2$, $ω^2 = ω_0^2 + 2αθ$

Dinámica (Dynamics)

Leyes de Newton (Newton's Laws)

• 1st Law: Inertia
• 2nd Law: $\sum \overrightarrow{F} = m \overrightarrow{a}$
• 3rd Law: Action and reaction

Trabajo y energía (Work and Energy)

• $W = \overrightarrow{F} \cdot \overrightarrow{d} = Fd \cos θ$
• $E_c = \frac{1}{2} m v^2$ (Kinetic energy)
• $E_p = mgh$ (Potential energy)
• $E_{el} = \frac{1}{2} k x^2$ (Elastic potential energy)

Potencia (Power)

• $P = \frac{W}{Δt} = \overrightarrow{F} \cdot \overrightarrow{v}$

Estática (Statics)

• Conditions for equilibrium: $\sum F_x = 0$, $\sum F_y = 0$, $\sum M = 0$

Impulso y cantidad de movimiento (Impulse and Momentum)

• $\overrightarrow{I} = \overrightarrow{F} Δt$ (Impulse)
• $\overrightarrow{p} = m \overrightarrow{v}$ (Momentum)
• $\overrightarrow{I} = Δ\overrightarrow{p}$

Gravitación (Gravitation)

• $F = G \frac{m_1 m_2}{r^2}$ (Gravitational force)
• $g = G \frac{M}{r^2}$ (Gravitational acceleration)
• $E_p = -G \frac{m_1 m_2}{r}$ (Gravitational potential energy)

Constantes (Constants)

• $g = 9.8 m/s^2$
• $G = 6.67 \times 10^{-11} Nm^2/kg^2$

Numerical Methods for Solving Differential Equations

• Finite Difference Method (FDM)
• Finite Volume Method (FVM)
• Finite Element Method (FEM)

Spectral Method (Main Idea)

• Expresses the solution using a set of global basis functions.
• Solution satisfies the equation at certain points.

Example Problem

• Equation: $\frac{d^2 u}{dx^2} = f(x), \quad x \in [a, b]$.
• Boundary conditions: $u(a) = \alpha, \quad u(b) = \beta$.

Assumed Solution

• $u(x) = \sum_{k=1}^{N} a_k \phi_k(x)$
• $\phi_k(x)$ are the basis functions.

Basis Function Choices

• Polynomials: $\phi_k(x) = x^k$.
• Trigonometric functions: $\phi_k(x) = e^{ikx}$.
• Legendre polynomials.
• Chebyshev polynomials.

Methods to Determine Coefficients $a_k$

• Collocation method: Solution satisfies the equation at certain points.
• Galerkin method: Require the residual to be orthogonal to the basis functions.
• Tau method: Combines collocation and Galerkin methods.

Collocation Method (Main Idea)

• Solution satisfies the equation at certain points.

Collocation Example

• Equation: $\frac{d^2 u}{dx^2} = f(x), \quad x \in [a, b]$.
• Boundary conditions: $u(a) = \alpha, \quad u(b) = \beta$.
• Assumed solution: $u(x) = \sum_{k=1}^{N} a_k \phi_k(x)$.

Discretization

• Divide the domain $[a, b]$ into $N$ points: $x_1, x_2, \cdots, x_N$.

Equation Satisfaction

• $\frac{d^2 u}{dx^2}(x_i) = f(x_i), \quad i = 1, 2, \cdots, N$

Boundary Conditions

• $u(a) = \alpha, \quad u(b) = \beta$

Matrix Form

• $A \mathbf{a} = \mathbf{f}$

Elements Defined

• $A_{ij} = \frac{d^2 \phi_j}{dx^2}(x_i)$
• $\mathbf{a} = [a_1, a_2, \cdots, a_N]^T$
• $\mathbf{f} = [f(x_1), f(x_2), \cdots, f(x_N)]^T$