My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Algorithms

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
Big-Oh 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!
alka2303 is offline  

My Computer Forum is free to register and we welcome everyone!

April 30th, 2010, 02:12 PM   #2
Joined: Apr 2010
Posts: 96
Re: Big-Oh 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)
asbo is offline  
November 19th, 2011, 03:31 PM   #3
Posts: n/a
Re: Big-Oh Proof

Thank you very much! Yea, I do the same thing haha - but sometimes the constants throw me off!

  My Computer Forum > Computer Science Forum > Algorithms

bigoh, proof

Thread Tools
Display Modes

Copyright © 2018 My Computer Forum Forum. All rights reserved.