Proving O(1) is the Same as O(2)

  • Thread starter Thread starter hholzer
  • Start date Start date
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 2K views
hholzer
Messages
36
Reaction score
0
I'm not sure if there is another more appropriate place to ask this question but here it is:
Prove that O(1) is the same as O(2)

O(1) would be the same as O(2) in the sense that for all n, given the constant functions
f(n) = c_1, and g(n) = c_2 we have f(n) <= g(n), yes? Or should "same" be taken more
literally here? If so, then in what way would we prove this?
 
Physics news on Phys.org
The Wikipedia article on big O notation may be useful here. I think you could use the formal definition to prove that any function which is O(1) is also O(2), and vice-versa, which seems like a reasonable "sameness condition" to me.