1

Having trouble with a homework problem on time complexity, how do you properly proof the equation. Everything I've done so far leads me to dead ends.

Question as listed:

Let f(n) and g(n) be non-negative functions such that f(n) is O(g(n)) and g(n) is O(f(n)). Use the definition of “big Oh” to prove that f(n) − g(n) is O(f(n)).

Maytham Fahmi
  • 31,138
  • 14
  • 118
  • 137
Ethan Biswurm
  • 13
  • 2

1 Answers1

0

Without outright giving you the answer to your homework, I'll rather push you to the right place. 1. Prove that f(n) = Θ(g(n)) iff g(n) = Θ(f(n)) 2. http://web.cse.ohio-state.edu/~lai.1/780-class-notes/2.math.pdf

Here are some notes to read over and after that working out the proof shouldn't be hard. Also, I'd ask this question on the math stack exchange and not stack overflow.

Xhuliano Brace
  • 121
  • 1
  • 9