DTG-2 Flashcards
What is a algorithm?
In computer science, an algorithm is a step-by-step set of instructions for solving a problem or performing a task. It is essential for programming and helps computers process data efficiently.
What does it mean for
f(x)∈O(g(x))?
Let f,g:R→R (or f,g:N→R) be two functions.
We write f(x)∈O(g(x)) if there are constants
C and k such that: ∣f(x)∣≤C∣g(x)∣∀x>k.
What is Big-O Notation used for?
Big-O Notation is used to describe the growth rate of an algorithm’s time or space requirements as the size of the input increases. It focuses on how performance scales with larger inputs, ignoring small details or constants.
What does O(n) mean?
O(n) means the time or space grows linearly with the size of the input. Example: If you process n items, the work takes proportional time, like frosting n cookies.
Which is faster: O(n) or O(n²), and why?
O(n) is faster than O(n²) because O(n) grows at a steady rate, while O(n²) grows much faster as the input size increases.
Example: O(n) = frosting cookies one by one; O(n²) = comparing every cookie with every other cookie.
Define: O(1), O(n), O(n^2), and O(2^n)
O(1): Constant time – Same time regardless of input size.
Example: Accessing an array element.
O(n): Linear time – Grows proportionally with input.
Example: Loop through a list.
O(n²): Quadratic time – Time grows as the square of input.
Example: Nested loops.
O(2ⁿ): Exponential time – Time doubles with each input.
Example: Finding all subsets.
Why Do We Avoid O(2ⁿ)?
Algorithms with O(2ⁿ) are often impractical for large inputs. Instead, computer scientists try to come up with better, more efficient algorithms to solve the same problem in polynomial time.
