A) Big-O notation and loop invariants1. Let g(n) be a function. For each of the following statements, mark in the answer sheetswhether it is correct (true = correct, false = incorrect).(a) Θ(g) = {f (n) : There exist positive constants c1, c2 and n0 such that0 ≤ c1 · g(n) ≤ f (n) ≤ c2 · g(n), for all n ≥ n0}(b) Θ(g) = {f (n) : There exist positive constants c1, c2 and n0 such that0 ≤ c1 · f (n) ≤ g(n) ≤ c2 · f (n), for all n ≥ n0}(c) Θ(g) = O(g) ∩ Ω(g)
Question
A) Big-O notation and loop invariants1. Let g(n) be a function. For each of the following statements, mark in the answer sheetswhether it is correct (true = correct, false = incorrect).(a) Θ(g) = {f (n) : There exist positive constants c1, c2 and n0 such that0 ≤ c1 · g(n) ≤ f (n) ≤ c2 · g(n), for all n ≥ n0}(b) Θ(g) = {f (n) : There exist positive constants c1, c2 and n0 such that0 ≤ c1 · f (n) ≤ g(n) ≤ c2 · f (n), for all n ≥ n0}(c) Θ(g) = O(g) ∩ Ω(g)
Solution
- Vamos a analizar cada una de las afirmaciones para determinar si son correctas o incorrectas.
(a) Θ(g) = {f(n) : Existen constantes positivas c1, c2 y n0 tales que 0 ≤ c1 · g(n) ≤ f(n) ≤ c2 · g(n), para todo n ≥ n0}
Para que una función f(n) esté en Θ(g), debe estar acotada tanto superior como inferiormente por g(n) multiplicada por constantes positivas. La definición dada en (a) cumple con esta condición, ya que establece que f(n) está entre c1 · g(n) y c2 · g(n) para n suficientemente grande.
Por lo tanto, la afirmación (a) es correcta (true).
(b) Θ(g) = {f(n) : Existen constantes positivas c1, c2 y n0 tales que 0 ≤ c1 · f(n) ≤ g(n) ≤ c2 · f(n), para todo n ≥ n0}
Esta afirmación también describe que f(n) está acotada tanto superior como inferiormente por g(n)
Similar Questions
1. Let g(n) be a function. For each of the following statements, mark in the answer sheetswhether it is correct (true = correct, false = incorrect).(a) Θ(g) = {f (n) : There exist positive constants c1, c2 and n0 such that0 ≤ c1 · g(n) ≤ f (n) ≤ c2 · g(n), for all n ≥ n0}(b) Θ(g) = {f (n) : There exist positive constants c1, c2 and n0 such that0 ≤ c1 · f (n) ≤ g(n) ≤ c2 · f (n), for all n ≥ n0}(c) Θ(g) = O(g) ∩ Ω(g)
For each of the following statements, mark in the answer sheets whether the statement istrue or false.(a) Let f and g be positive functions. Then, f (n) + g(n) ∈ O(n) implies that f ∈ O(n)and g ∈ O(n).(b) There exist functions f, g ∈ Ω(n) such that f − g ∈ Ω(g) and 2g − f ∈ Ω(f ).
Which of the following statements is FALSE about Big O notation?Group of answer choicesIt can be used to compare the efficiency of different algorithmsIt ignores constant factors.It considers only the dominant/leading term as the input size grows.It represents the worst-case time complexity.
If f(n) = O(g(n)), which of the following statements is true?g(n) grows faster than f(n) as n increasesf(n) grows faster than g(n) as n increasesf(n) and g(n) grow at the same rate as n increasesNone of the above
Prove the following assertions by using the definitions of the notations in-volved, or disprove them by giving a specific counterexample.a. If t (n) ∈ O(g(n)), then g(n) ∈ (t (n)).b. (αg(n)) = (g(n)), where α > 0.c. (g(n)) = O(g(n)) ∩ (g(n)).d. For any two nonnegative functions t (n) and g(n) defined on the set ofnonnegative integers, either t (n) ∈ O(g(n)), or t (n) ∈ (g(n)), or both
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.