Asymptotic time and space complexity analysis, Big-O / Big-Omega / Big-Theta notation, recurrence relations (Master Theorem), algorithmic design paradigms (divide-and-conquer, greedy methods, dynamic programming), and graph algorithms.
Lecture 5: Complexity of Iterative Algorithms (Part 2)
3-step complexity calculation method, quadratic sorting analysis (Selection Sort & optimized Bubble Sort with triangular sums), best/worst/average cases (Linear Search), $O(n \cdot m)$ nested loops, $O(\sqrt{n})$ primality testing, Two Pointers technique, and 10 solved exercises with interactive live step simulators.
Lecture 6: Complexity of Algorithms & Data Structures
Impact of data structures on computational complexity: contiguous vs. linked memory, dynamic array resizing & amortized analysis, stacks & circular queues ($O(1)$ operations), binary search trees (BST), binary heaps & priority queues, hash tables (collisions, open addressing, rehashing), and comparative complexity trade-offs with solved exercises.
Lecture 6.b: Complexity of Recursive Algorithms
From iterative limits to recursive functions, modeling recurrence relations ($T(n) = aT(n/b) + f(n)$), building and analyzing recursion trees (Factorial, Merge Sort, Binary Search), and mastering the Master Theorem (intuition of the 3 cases, root vs. leaves battle, and applicability rules).
Lecture 7: Introduction to P Problems
Complexity of computational problems vs. algorithms, definition of the P complexity class, polynomial time vs. super-polynomial/exponential growth, tractability (Cobham's thesis), decision vs. optimization problems, input encoding, and classic problems in P with solved exercises. Inclui simulador gráfico interativo do Slide 16 (2ⁿ vs n³ e n²).