MHB What Are the Time Complexities of These Functions?

[shamieh]

View attachment 4731
Can someone tell me if I'm even doing this correctly? I haven't dealt with TCs in while.
So I got:

$a) h_1(n) = O(n) \implies n$ , $h_2(n) = \Omega (n\log n) \implies n\log n$

$b) h_1(n) = \Omega(\log n) \implies \log n$, $h_2(n) = O(n^{2/5}) \implies n^{2/5}$

(Justification $h_1(n)$: Let $n = 1000 \implies 12(1000)^{2/3} = 524$ and Let $x = 1000 \implies 7 \log(1000) = 48$ so $n^{2/5} > \log(n)$)

(Justification $h_2(n)$: Let $n = 1000 \implies (5(100000000))^{2/5} = 3017.08..$ so $n^{2/5} > O(1)$ (or 1000) )

$c) h_1(n) = O(n^2) \implies n^2$, $h_2(n) = \Omega(n \log^4 n) \implies n \log^4 n$

$d) h_1(n) = O(\log(n)) \implies \log(n)$, $h_2(n) = \Omega (\log(n^5)) \implies \log(n^5)$

$e) h_1(n) = O(n) \implies n$, $h_2(n) = O(n) \implies n$

(Justification $h_1(n)$: let $n = 1000 \implies 1000^{1.02} = 1148.15 > \log(1000)^{1.02} = 7.17..$)

(Justification $h_2(n)$: let $n = 1000$ to find $1000(1000)log^3 1000 = 3.296.. < 2(1000) = 2000$)

$f) h_1(n) = O(n^2) \implies n^2$, $h_2(n) = \Omega(\log n) \implies \log n$

(Justification $h_1(n)$: Well $O(n^2) = n^2$ ?)

(Justification $h_2(n)$: $O(\log n) = \log n$) ?

$h) h_1(n) = O(n) \implies n$, $h_2(n) =$ exponential?

 

[Ackbach]

$a) h_1(n) = O(n) \implies n$ , $h_2(n) = \Omega (n\log n) \implies n\log n$

You want to format these the way the problem is asking: $h_1(n)=n$, because $1000n-1000=O(n)$. And $h_2(n)=n \, \log(n)$ because $2n \, \log(n)+6n=O(n \, \log(n))$.

$b) h_1(n) = \Omega(\log n) \implies \log n$, $h_2(n) = O(n^{2/5}) \implies n^{2/5}$

(Justification $h_1(n)$: Let $n = 1000 \implies 12(1000)^{2/3} = 524$ and Let $x = 1000 \implies 7 \log(1000) = 48$ so $n^{2/5} > \log(n)$)

$n^{2/3}$ beats $\log(n)$, so you need to have $h_1(n)=n^{2/3}$.

(Justification $h_2(n)$: Let $n = 1000 \implies (5(100000000))^{2/5} = 3017.08..$ so $n^{2/5} > O(1)$ (or 1000) )

$c) h_1(n) = O(n^2) \implies n^2$, $h_2(n) = \Omega(n \log^4 n) \implies n \log^4 n$

$d) h_1(n) = O(\log(n)) \implies \log(n)$, $h_2(n) = \Omega (\log(n^5)) \implies \log(n^5)$

Don't forget the logarithm rule here: $\log(n^5)=5 \, \log(n)$.

$e) h_1(n) = O(n) \implies n$, $h_2(n) = O(n) \implies n$

This isn't going to work, I'm afraid. On the first one, you need $h_1(n)=n^{1.02}$. Inside the parentheses, the $n$ beats the $\log(n)$, but without the correct exponent, it will not grow fast enough. For $h_2(n)$, you have to have $n \, \log^3(n)$. Exponentiating the logarithm does not have the nice identity that $\log(n^m)=m \, \log(n)$ does.

(Justification $h_1(n)$: let $n = 1000 \implies 1000^{1.02} = 1148.15 > \log(1000)^{1.02} = 7.17..$)

(Justification $h_2(n)$: let $n = 1000$ to find $1000(1000)log^3 1000 = 3.296.. < 2(1000) = 2000$)

$f) h_1(n) = O(n^2) \implies n^2$, $h_2(n) = \Omega(\log n) \implies \log n$

(Justification $h_1(n)$: Well $O(n^2) = n^2$ ?)

(Justification $h_2(n)$: $O(\log n) = \log n$) ?

For $h_2(n)$, you're going to need
$$5^{\log(n)}=\left(10^{\log(5)}\right)^{\log(n)}=10^{\log(5)\cdot\log(n)}=10^{\log\left(n^{\log(5)}\right)}=n^{\log(5)}.$$
You can see here that I've assumed you're using $\log(x)=\log_{10}(x)$. What follows is more general, in case you're using a different base:
$$a^{\log_b(x)}=\left(b^{\log_b(a)}\right)^{\log_b(x)}=b^{\log_b(a) \cdot \log_b(x)}=b^{\log_b\left(x^{\log_b(a)}\right)}=x^{\log_b(a)}.$$
So, in general, $a^{\log_b(x)}=x^{\log_b(a)}.$ I did not know that before now!

$h) h_1(n) = O(n) \implies n$, $h_2(n) =$ exponential?

I think you're going to need more of something like this:
$$n^{\sqrt{n}}=n^{n^{1/2}}=\left(10^{\log(n)}\right)^{n^{1/2}}=10^{n^{1/2}\log(n)}.$$
That's in the format you need for $h_1$. You can do a similar trick for $h_2$.

 

[shamieh]

Wow thanks so much.. So now I'm on the second part.. (NOTE: I left out $h$ for the time being)

View attachment 4734

But I'm not sure if I'm doing it right. Here is what I have so far:
a) $f_1 = O(f_2)$
b) Not Equal
c) Not Equal
Justification: $n^2 = 1000^2 =$ 1 million while $(1000)\log^4 (1000) = 2.27..$ so we know that $f(x) \notin O(g(x))$
d) $f_1 = O(f_2)$
Justification: $ \log(n) = \log(1000) = 6.907..$ and $ \log(n^5) = 34.538..$ so we know that $f(x)=O(g(x))$ iff $∃$ positive constants $C$ and $n_0 |0≤f(n)≤c∗g(n)$, $∀$ $ n≥n_0| $ $\therefore f_1 = O(f_2)$
e) $f_1 = O(f_2)$
f) Not Equal

 

[shamieh]

a) $f_1 = O(f_2)$
b) $f_1 = O(f_2)$
c)
According to the definition I know that: $f(x)=O(g(x))$ iff $∃$ positive constants $C$ and $n_0 |0≤f(n)≤c∗g(n), ∀ n≥n_0|$

So letting $n = 10$, $c = 5$ for:

$0 \le f_1(n) \le c * f_2(n) \implies (10)^2 + (10)\log(10) \le (5)((10)\log^4 (10) + \sqrt{10})$
= $0 \le 123 \le 1405 \implies f_1 = O(f_2)$

Using the fact that:

View attachment 4736

Then we know that $\lim_{n\rightarrow\infty}$ $\frac{n^2 + n \log n}{n \log ^4 n + \sqrt{n}} = \infty$

$\therefore f_1 = \Omega(f_2) \implies f_1 = \Theta(f_2)$

d)
According to the definition I know that: $f(x)=O(g(x))$ iff $∃$ positive constants $C$ and $n_0 |0≤f(n)≤c∗g(n), ∀ n≥n_0|$

So letting $n = 10$, $c = 5$ for:

$ 0 \le f_1(n) \le c * f_2(n) \implies 3\log(10) + 3 \le (5)(\log (10^4) + 2)$
= $0 \le 9.9077 \le 56.05 \implies f_1 = O(f_2)$

Using the fact that:

View attachment 4736

Then we know that $\lim_{n\rightarrow\infty}$ $\frac{3\log(n) + 3}{\log(n^5) + 2} = \frac{3}{5}$

$\therefore f_1 = \Theta(f_2)$

e)
$f_1 = O(f_2)$
$\therefore f_1 = \Omega(f_2) \implies f_1 = \Theta(f_2)$

f)
$f_1 = O(f_2)$
$\therefore f_1 = \Omega(f_2) \implies f_1 = \Theta(f_2)$

h) According to the definition I know that: $f(x)=O(g(x))$ iff $∃$ positive constants $C$ and $n_0 |0≤f(n)≤c∗g(n), ∀ n≥n_0|$

So letting $n = 10$, $c = 1$ for:

$ 0 \le f_1(n) \le c * f_2(n) \implies 10^{\sqrt{10}} + 3 \le (1)(sqrt{10}^{10})$
= $0 \le 1453 \le 100,000 \implies f_1 = O(f_2)$

Using the fact that:

View attachment 4736

Then we know that $\lim_{n\rightarrow\infty}$ $\frac{n^{\sqrt{n}}}{\sqrt{n}^{n}} = 0$
$\therefore f_1 \in O(f_2)$ but $f_1 \ne \Omega(f_2), f_1 \ne \Theta(f_2)$