Algorithms and Data Structures

• An algorithm involves step-by-step procedures for problem-solving
• Data structure is how data is organized in memory
• Studying algorithms improves problem-solving skills and is vital in computer science
• Algorithms are relevant for companies like Google, Microsoft, Facebook, and Amazon
• Knowledge of algorithms keeps you competitive in the job market

Course Coverage

• Basic data structures like Arrays, Linked lists, Stacks, Queues, Trees, Graphs, and Hash tables will be covered
• Basic algorithms will be discussed: Sorting, Searching, Graph algorithms, String algorithms, Dynamic programming
• Algorithm analysis using asymptotic notation and recurrence relations is also covered
• Algorithm design techniques include divide and conquer and greedy algorithms

Algorithm Analysis

• An algorithm should produce the correct result
• Efficiency is how an algorithm uses resources
• Time complexity measures how long an algorithm takes
• Space complexity gauges the memory an algorithm requires

Asymptotic Notation

• Asymptotic Notation describes the function's limiting behavior
• It describes algorithm running time as input size grows
• Types include Big O, Big Omega, and Big Theta notation

Big O Notation

• $O(g(n)) = { f(n)$: there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le cg(n)$ for all $n \ge n_0 }$
• Big O notation describes the upper bound of an algorithm's running time
• For $f(n) = 3n + 2$, $f(n) = O(n)$

Common Time Complexities

• $O(1)$ is constant time
• $O(log n)$ is logarithmic time
• $O(n)$ is linear time
• $O(n log n)$ is linearithmic time
• $O(n^2)$ is quadratic time
• $O(n^3)$ is cubic time
• $O(2^n)$ is exponential time
• $O(n!)$ is factorial time

Calculating Time Complexity

• Identify the input size
• Count the number of operations
• Express operations as a function of input size
• Remove constants and lower-order terms

Example Time Complexity Calculation

• In the provided C++ code example, int sum = 0; is $O(1)$
• for (int i = 1; i <= n; i++) has $O(n)$ operations
• sum += i; is $O(1)$
• return sum; is $O(1)$
• Total time complexity is $O(1) + O(n) * O(1) + O(1) = O(n)$