Intro and Asymptotic Notation and Complexity Flashcards
What does the Big-O notation represent
The upper bound (worst case) on the growth rate of an algorithm’s running time
What does Θ(theta) notation represent
It gives the tight (exact) bound, both upper and lower, on an algorithms growth
What is the relationship between f(n) = o(g(n)) and f(n) = O(g(n))?
If f(n) = o(g(n)), then f(n) is strictly smaller than g(n) for large n, and it also implies f(n) = O(g(n))
Order the following by growth (ascending): O(log n), O(n), O(n log n), O(n²), O(2ⁿ)
O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
Solve: T(n) = T(n-1) + n
O(n²) — it expands to an arithmetic series.
What is the Master Theory format
T(n) = aT(n/b) + f(n)
What’s the complexity of T(n) = 2T(n/2) + n?
O(n log n) → classic Merge Sort recurrence.
What is an algorithm
A finite sequence of unambiguous introuctions to solve a problem
Solve T(n) = T(n/2) + log n
O(log² n) — Use recursion tree; Master Theorem doesn’t apply directly.
Solve T(n) = 4T(n/2) + n
O(n²) — Master Theorem, Case 1: f(n) = O(n^(log_b a - ε)) → log₂4 = 2
What is the complexity of T(n) = T(n/4) + n²?
O(n²) — Master Theorem, Case 3 (f(n) dominates)
Can the Master Theorem solve T(n) = T(n/2) + n log n?
No — f(n) = n log n does not fit Case 1, 2, or 3 directly.
What is the condition for applying the Master Theorem?
T(n) = aT(n/b) + f(n), with constants a ≥ 1, b > 1 and f(n) positive.
What is sedgewicks definition of an algorithm
describes methods for solving problems that are suited for computer implementation
What is Aho, hopcroft and ultman definition of an algorthm
a finite sequence of intructions which have a clear meaning and cen be performed with a finite amount of effort in a finite length of time
What is wikapedias definition of an algorthm
an algorithm is a finite sequence of mathematically rigourous instructions, used to solve a of class of specific problems or to perform computation
What is levins definition of an algorithm
a finite sequence of instructions of unabiguous intrions for solving as problem
What is the GCD
gives largest natural number that divides two numbers, can be found with the GCD
Is the function 100n+5 = O(n2
)
a) Yes
b) No
c) Only for large values of n
d) Only for small values of n
e) Can’t be determined
yes is correct because O(n²) includes all functions that grow slower or equal to n² in the long run.
What are the 7 growth functions
- Constant time
- Logarithmic, log n
- Linear, n
- Polylogarithmic, n^k logn
- Quadratic, n^2
- Cubic, n^3
- Exponential
What is a constant time growth function
for example so,ething that returns a element
What is a logirithmic growth function
occurs in algorithms that transform a bigger problem into a smaller problem, input size a ration of the original problem
What is a linear growth function
Algorithms that are forced to pass through all element sof the input (of size n) a number (constant) times yeild linear running time
What is a polylogarithmic growth function
an algorthm that breaks the problem into smaller parts, solves the problem for the smaller parts and then combines the solution
What is the worst case
where the input is the worst case input of size n for which the algorithm runs the longest amoung all possible inputs of that size
What is the best case
best case input size for which the alghorithm runs the fastest amoung all inputs of that size
What is the average case
neither the worst nor the best case running, given by the average case efficiency of an algorithm.
