
Algorithms Algorithms and Data Structures  Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum 
 LinkBack  Thread Tools  Display Modes 
November 13th, 2009, 02:31 PM  #1 
Joined: Nov 2009 Posts: 1  BigOh Proof
Hey, I'd like a little help on proving that g(n) = 2^n is not bounded above by f(n) = n. Here we need to to prove that for all positive reals c, for all natural numbers B, there exists a natural number n such that n >= B and g(n) > cf(n). So, for this proof my prof chose n = 2(the ceiling of log(c) + B + 1), (note that it is log base 2). I tried to reason out his choice of n, but I am pretty stuck ops: . Clearly we need to write n in terms of c and B, but I get edgy whenever I deal with logs. Any help on the choice of n here would be so, so appreciated! 
My Computer Forum is free to register and we welcome everyone! 
April 30th, 2010, 02:12 PM  #2 
Joined: Apr 2010 Posts: 96  Re: BigOh Proof
I havent faced this personally but my old maths teacher told me 2 and 10 are the cleanest numbers when dealing with log's try going onto bbc or something as they will be use full...try searching wikipedia (as stupid as it sounds they have a lot of formula's and you can check it by other sites) 
November 19th, 2011, 03:31 PM  #3 
Guest Joined: Posts: n/a  Re: BigOh Proof
Thank you very much! Yea, I do the same thing haha  but sometimes the constants throw me off!
