My Math Forum Which function is bigger

 Algebra Pre-Algebra and Basic Algebra Math Forum

 November 8th, 2009, 04:05 PM #1 Member   Joined: Sep 2008 Posts: 41 Thanks: 0 Which function is bigger Hopefully this is the correct forum for this. Let $\lg(x)= \log_2(x)$. I have an algorithm that I need to show makes at most $n + 2 \left \lceil\lg(n-1) \right \rceil - 3$ comparisons, where $n$ is related to the input size. I have determined that the algorithm makes $n + 2 \left \lceil\lg(n) \right \rceil - 4$ comparisons, so I can increase its number of comparisons to $n + 2 \left \lceil\lg(n) \right \rceil - 3$. So the only thing different is $\left \lceil\lg(n) \right \rceil$ vs $\left \lceil\lg(n-1) \right \rceil$. Is it true that $\left \lceil\lg(n) \right \rceil \le \left \lceil\lg(n-1) \right \rceil$? If that's the case then I arrive at the required result. I have been graphing the functions using an online applet that seems to show they are "identical", but I can't determine if the first one is less than or equal to the second one. This specific question I am working on didn't mention asymptotic bounds, it's more of finding the exact number (otherwise it's just $O(n)$). Thanks
 November 8th, 2009, 04:56 PM #2 Global Moderator   Joined: Dec 2006 Posts: 18,841 Thanks: 1564 If n = 3, $^{n\,+\,2\lceil\lg(n\,-\,1)\rceil\,-\,3\,=\,2,}$ but $^{n\,+\,2\lceil\lg(n)\rceil\,-\,4\,=\,3.}$
 November 8th, 2009, 06:01 PM #3 Member   Joined: Sep 2008 Posts: 41 Thanks: 0 Re: Which function is bigger Thanks for your response. So basically I am stuck with what I have, and have to look for a different way? I.e., what I have doesn't satisfy the requirement, because right now it performs (slightly) more comparisons.
 November 8th, 2009, 09:13 PM #4 Global Moderator   Joined: Dec 2006 Posts: 18,841 Thanks: 1564 Very possibly. It's difficult to say more unless you disclose all the details.
 November 9th, 2009, 08:39 AM #5 Member   Joined: Sep 2008 Posts: 41 Thanks: 0 Re: Which function is bigger I think the only remaining details is the algorithm itself. Ill probably try and ask for hints from classmates or the professor. I just wanted to get working on it on the weekend was over, and didnt have those resources until then. If youre interested, the algorithm is to find the 3rd largest of a list of $n$ distinct elements, for example $n$ distinct natural numbers.

 Tags bigger, function

,

# which function is bigger

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post msgelyn Number Theory 2 January 12th, 2014 03:13 AM BenFRayfield Real Analysis 0 May 31st, 2013 07:40 AM gelatine1 Algebra 2 December 29th, 2012 12:09 AM Albert.Teng Algebra 8 April 24th, 2012 04:17 AM W300 Algebra 2 October 22nd, 2009 09:11 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top