Final answer:
To demonstrate that an algorithm's running time is o(g(n)) if and only if its worst-case is o(g(n)) and best-case is ω(g(n)), it's necessary to understand that o(g(n)) represents an upper bound, and ω(g(n)) a lower bound on the running time. The worst-case can't exceed, and the best-case can't be less than their respective bounds, which implies that running time generally falls within o(g(n)). The proof establishes that running time adheres to o(g(n)) using these definitions.
Step-by-step explanation:
To prove that the running time of an algorithm is o(g(n)) if and only if its worst-case running time is o(g(n)) and its best-case running time is ω(g(n)), we need to understand the definitions of these complexity classes. Big O, written as o(g(n)), describes an upper bound on the running time of an algorithm, meaning the running time grows at most as fast as a function g(n) for large enough n. Similarly, Big Omega, written as ω(g(n)), describes a lower bound, indicating the running time grows at least as fast as g(n) for large enough n.
First, assume that the running time of an algorithm is o(g(n)). This implies that in the worst case, the running time must also be o(g(n)), since the worst-case running time cannot exceed the general upper bound implied by o(g(n)). Additionally, the best-case running time should be ω(g(n)), as the algorithm's running time cannot be universally lesser than g(n) if it's sometimes growing at the rate of g(n).
Conversely, if the worst-case running time is o(g(n)) and the best case is ω(g(n)), it implies that the running time of the algorithm always lies between these two bounds. Consequently, we can deduce that the algorithm's running time is o(g(n)), since all running times (inclusive of the best and worst cases) are bounded by g(n), satisfying the definition of the o(g(n)) complexity class.
Therefore, we have proven that the algorithm's running time is o(g(n)) if and only if its worst-case running time is o(g(n)) and its best-case running time is ω(g(n)).