Algorithms Exam 1

little omega formal definition

{f(n): for all constants c > 0, there exists a constant n₀ > 0 such that 0 ≤ cg(n) < f(n) for all n ≥ n₀}

little o formal definition

{f(n): for all constants c > 0, there exists a constant n₀ > 0 such that 0 ≤ f(n) < cg(n) for all n ≥ n₀}

Big O formal definition

{f(n): there exists constants c, n₀ > 0 such that 0 ≤ f(n) < cg(n) for all n ≥ n₀}

Big Omega formal definition

{f(n): there exists constants c, n₀ > 0 such that 0 ≤ cg(n) < f(n) for all n ≥ n₀}

Big Theta formal definition

{f(n): there exists constants c₁, c₂ ,n₀ > 0 such that 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n) for all n ≥ n₀}

b^log_b(a)

a

log_c(ab)

log_c(a) + log_c(b)

log_b(aⁿ)

nlog_b(a)

log_b(a)

(log_c(a))/(log_c(b))

log_b(1/a)

-log_b(a)

1/log_a(b)

log_b(a)

a^{log_b(c )}

c^log_b(a)