对于两个非负函数f和g，证明或反证f= O(g)和g= O(f)且∀n，f(n) > g(n)则f−g= O(1)

首先，我们来解释一下问题中提到的符号和概念：

• O符号：在计算机科学中，O符号表示算法的渐进时间复杂度的上界。当我们说f=O(g)时，意味着存在一个正常数c和一个正整数n0，使得对于所有的n≥n0，都有f(n)≤c*g(n)。这表示函数f的增长速度不超过函数g的增长速度。

现在我们来证明或反证f=O(g)和g=O(f)且∀n，f(n) > g(n)则f−g=O(1)。

证明： 根据题目条件，我们知道f=O(g)和g=O(f)，即存在正常数c1、c2和正整数n1、n2，使得对于所有的n≥n1，有f(n)≤c1g(n)，对于所有的n≥n2，有g(n)≤c2f(n)。

我们需要证明f−g=O(1)，即存在正常数c和正整数n0，使得对于所有的n≥n0，有|f(n)−g(n)|≤c。

由于∀n，f(n) > g(n)，我们可以推断出f(n)−g(n) > 0，即f(n)−g(n)是一个非负函数。

我们可以选择c=max(c1, c2)作为正常数，并选择n0=max(n1, n2)作为正整数。

对于所有的n≥n0，根据f=O(g)和g=O(f)的定义，我们有f(n)≤c1g(n)和g(n)≤c2f(n)。

因此，我们可以得到以下不等式：

f(n)−g(n) ≤ c1g(n)−g(n) ≤ (c1−1)g(n) ≤ c*g(n)

g(n)−f(n) ≤ c2f(n)−f(n) ≤ (c2−1)f(n) ≤ c*f(n)

由于f(n)−g(n) > 0，我们可以得到：

0 ≤ f(n)−g(n) ≤ c*g(n)

因此，我们证明了f−g=O(1)。

综上所述，我们证明了对于两个非负函数f和g，如果f=O(g)和g=O(f)且∀n，f(n) > g(n)，则f−g=O(1)。