This question is around computer science, but too mathmatichal to ask anywhere else. The log is base 2.
These are the two given functions:
$g(n) = 2^{\lg^2n}$
$f(n) = \sum_{i=1}^{n^2}\lg\left(i\right)$
After simplifying the term $2^{\lg^2n}$ to be $n^{\lg (n)}$ , so I can say that: $g(n) = \theta(n^{\lg (n)})$, and due to $f(n) = \sum_{i=1}^{n^2}\lg\left(i\right)$ being a sum function I can infer it is "boiling down" to the sum of an arithmetic sequence, which means I can say:
$f(n) = \theta(n^2)$
I am being asked to determine what are the asymptotic relationships between g and f.
I can infer both functions are of the same order, which is $n$ raised to the power of a number.
So, let's say I want to show that $g(n) = \theta(f(n))$:
So I have to show that there are positive constants known as $c_1$, $c_2$, and $n_0$, so that for every $n\ge n_0$, the following is true:
$c_1f(n) \le g(n) \le c_2f(n)$
I'll try to prove it for the right side of the inequality. I heard enlarging the expression and finding constants is the way to prove it. So, can I just enlarge the original expression to something big enough that will be $\le$ to the original one for every $n\ge 1$ ?
And that means I found $c_2 = 100$, and $n_0 = 1$?
$n^{\lg (n)} \le 100n^2$
Same line of taught will be on this side, but the opposite:
$0.5n^2 \le n^{\lg (n)}$
just taking a function that grows slow enough with the same order of $n^2$.
So it means there are $c_1=0.5$, and $n_0 = 1$?
And assuming it is done correctly, I can also infer that $g(n) = O(f(n))$, because I have, supposedly, found a $c=100$, and $n_0 = 1$ positive constants so that $g(n) \le cf(n)$ is true.
And by the same logic, infer $g(n) = \Omega(f(n))$, because I have, supposedly, found a $c=0.5$, and $n_0 = 1$ positive constants so that $cf(n) \le g(n)$.
So that means the asymptotic relationships between $g$ and $f$ are $O$ (big O), $\Omega$, and $\theta$?