If $f(n)$ $\in$ $O(g(n))$ and $O(h(n))$ $\subset$ $O(g(n))$, Can we say that in general $f(n)$ $\not\in$ $O(h(n))$

Question

I have this problem because I want to prove this.

For some $k\in \mathbb{Z}^+$, let $f(n) = \sum_{i=1}^{n} i^k$ and let $g(n) = n^k$, approve or disapprove that $f(n) \in O(g(n))$.

I did this. (I do not know other way, sorry, If this is TRUE plese help me.)

We know for any $k\in \mathbb{Z}^+$, for all $i \in \{1,2,3, \cdots,n\}$ and $n \in \mathbb{N}.$

$$i^k\leq n^k$$

So we have this.

$$\sum_{i=1}^{n} i^k \leq n \cdot n^k$$

and if I take $c=1$ and $n_0 = 1$, $f(n) \in O(n^{k+1})$. But we know $O(n^k) \subset O(n^{k+1})$, so Can I say that in general $f(n) \not\in O(n^k)$. And is all?.

Answer 1

The claim in your title is false: simply consider the case where $f=h$.

Consequently, your solution attempt also does not work. You have shown $f(n) \in O(n^{k+1})$ and $O(n^k) \subset O(n^{k+1})$, but this says nothing about whether $f(n) \in O(n^k)$ or not. It is like asking "I know dog $\in \{\text{animals}\}$ and $\{\text{mammals}\} \subset \{\text{animals}\}$, can I say that a dog is not a mammal?"

Following D. Thomine's hint, note that $$\sum_{i=1}^n i^k \ge \sum_{i=\lceil n/2 \rceil}^n i^k \ge \sum_{i=\lceil n/2 \rceil}^n (n/2)^k \ge (n/2)^{k+1}.$$ The right-hand side cannot be $O(n^k)$ because no constant $C>0$ satisfies $(n/2)^{k+1} \le C n^k$ for all large $n$.

Answer 2

Let's take $k=1$. Then we have $f(n) = \sum_{i=1}^{n} i= \dfrac{n(n+1)}{2}$, so $f \notin O(n)$.