Exercise IIX

  • Use the definition of Big Theta to show the asymptotic running time of a given program.

Consider the following function T(n)T(n) describes the precise running time of an algorithm:

T(n)=3n2−100n+6 T(n) = 3n^2 - 100n + 6


Exercise Show T(n)∈Θ(n2)T(n) \in \Theta(n^2).

Solution

We have shown in earlier lessons that T(n)∈O(n2)T(n) \in \Omicron(n^2) and T(n)∈Ω(n2)T(n) \in \Omega(n^2). Therefore, we can conclude T(n)∈Θ(n2)T(n) \in \Theta(n^2).

Exercise Show T(n)∉Θ(n)T(n) \notin \Theta(n).

Solution

We have shown earlier that T(n)∈Omega(n)T(n) \in Omega(n) but T(n)∉O(n)T(n) \notin \Omicron(n). Therefore, we can conclude T(n)∉Θ(n)T(n) \notin \Theta(n).

Exercise Show T(n)∉Θ(n3)T(n) \notin \Theta(n^3).

Solution

We have shown earlier lessons that T(n)∈O(n3)T(n) \in \Omicron(n^3) but T(n)∉Ω(n3)T(n) \notin \Omega(n^3). Therefore, we can conclude T(n)∉Θ(n3)T(n) \notin \Theta(n^3).