Turn on thread page Beta
    • Thread Starter
    Offline

    2
    ReputationRep:
    I realise this is more CompSci than maths, but the tech soc are stumped.

    So, there's this question

    I have multiple issues with it, so any hints would be much appreciated. I'm going to go through the bits I don't understand one at a time, so the stuff below doesn't actually ask how to get to the answer - I just want to clarify a step.

    I get
    T_A(3n)=9T_A(n) + O(n^2)
    T_A(9n)=9T_A(3n) + O(81n^2)=O(81n^2)+9O(9n^2)+81T_A  (n)
    Can I then simplify the second one to
    T_A(9n)=O(n^2)+81T_A(n)?
    The reason I hesitate is because of big-theta (i.e. exact bounds) - can I still remove constant factors from O(n^2)?

    Or have I got the wrong end of the stick completely?
    Offline

    18
    ReputationRep:
    I don't see an issue with removing constant factors here. (Doesn't mean I'm not missing something, of course).
    • Thread Starter
    Offline

    2
    ReputationRep:
    Ok then, final answers I get
    T_A(n) = O(n^2) + n^2
    T_B(n) = O(n) + 5^{log_2 n}?
    So that would mean that b is more efficient I believe.
    • Thread Starter
    Offline

    2
    ReputationRep:
    Please correct any mistakes!

    For the benefit of the person who actually wanted to know the answer to this question (and to help others who may come along -
    We have

    Using definition for T_A(n), we can expand
    T_A(3n) = 9T_A(3n/3) + O((3n)^2) = 9T_A(n) + O(9n^2)
    Applying the same theory again -
    T_A(9n) = 9T_A(9n/3) + O((9n)^2) = 9T_A(3n) + O(81n^2) = 9(9T_A(n) + O(9n^2)) + O(81n^2) = 81T_A(n) + 9O(9n^2) + O(81n^2)
    We can remove constant factors here (as reassured by Dfranklin above) (if you don't understand why 9O(9n) = O(n), your knowledge of big-O notation is patchy - I hesitated because of exact bounds). So
    T_A(3n) = 9T_A(n) + O(n^2)
    T_A(9n) = 81T_A(n) + O(n^2)
    From this, we can deduce (i.e. spot the pattern) the relation
    T_A(cn) =c^2T_A(n) + O(n^2)
    If we let n = 1
    T_A(c) =c^2 + O(n^2)
    T_A(n) =n^2 + O(n^2)
    Note that this does nothing to the big O term. The reason for this gap in logic is because my working is actually not entirely correct, but is close enough to be acceptable in a non-maths course I feel.

    (proof is not required in this question, but induction (preferably strong) is a possibility).

    A similar process is used for T_B(n). I have skipped steps in this one, but the theory is the same.

    T_B(2n) = O(n) + 5T_B(n)
    T_B(2n) = O(n) + 25T_B(n)
    T_B(2n) = O(n) + 125T_B(n)
    Again, by deduction
    T_B(n) = O(n) + 5^{log_2 n} = O(n) + 5^{\frac{log n}{log 2}} = O(n) + 5^{{\frac{log n}{log 2}}*{\frac{log 5}{log5}}} = O(n) + 5^{{\frac{log n}{log 5}}*{\frac{log 5}{log2}}} = O(n) + 5^{{\frac{log n}{log 5}}*{\frac{log 5}{log2}}} = O(n) + 5^{log_5 n*log_2 5} = O(n) + n^{log_2 5}

    {log_2 5} is larger than 2, and is therefore asymptotically larger than n^2. T_A is therefore the more efficient as it is O(n^2) vs O(n^2andabit).
    • PS Helper
    • Wiki Support Team
    Offline

    14
    PS Helper
    Wiki Support Team
    (Original post by Chrosson)
    x
    I think I can follow that, thanks :awesome:. Though, why are we substituting n for 3n, and then 9n? Are those arbitrary choices or do they come from somewhere?
    • Thread Starter
    Offline

    2
    ReputationRep:
    (Original post by secretmessages)
    I think I can follow that, thanks :awesome:. Though, why are we substituting n for 3n, and then 9n? Are those arbitrary choices or do they come from somewhere?
    They come from the fact that the formula includes n/3. Really speaking you only want to be dealing with integers, and you need to have some way of spotting the pattern - decimals/fractions is a poor way to go about it. If it was n/4 you would use 4n and 16n etc.
    Offline

    18
    ReputationRep:
    I disagree with your conclusion.

    Spoiler:
    Show
    Suppose g(x) = 5^{\log_2 x}

    What is g(2^k) and how does this compare with (2^k)^2?

    So, does g(n) grow faster or slower than n^2?
    • Thread Starter
    Offline

    2
    ReputationRep:
    (Original post by DFranklin)
    I disagree with your conclusion.

    Spoiler:
    Show
    Suppose g(x) = 5^{\log_2 x}

    What is g(2^k) and how does this compare with (2^k)^2?

    So, does g(n) grow faster or slower than n^2?
    Uh, bugger.
    5^k vs 4^k.
    Thanks for that. I'll factor that in now.

    (Original post by secretmessages)
    x
    I knew there had to be at least one mistake
    • PS Helper
    • Wiki Support Team
    Offline

    14
    PS Helper
    Wiki Support Team
    (Original post by Chrosson)
    Uh, bugger.
    5^k vs 4^k.
    Thanks for that. I'll factor that in now.


    I knew there had to be at least one mistake
    The principle's the same though right? That's what I needed to know most, by example. Very helpful both of you
    • Thread Starter
    Offline

    2
    ReputationRep:
    (Original post by DFranklin)
    I disagree with your conclusion.

    Spoiler:
    Show
    Suppose g(x) = 5^{\log_2 x}

    What is g(2^k) and how does this compare with (2^k)^2?

    So, does g(n) grow faster or slower than n^2?
    Thanks for the correction, the outcome is correct now but the working may not be :unsure:. I'll have to check tomorrow. Too late now.
    Also, the latex limit is kinda irritating.
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: January 14, 2010

University open days

  • University of Exeter
    Undergraduate Open Days - Exeter Campus Undergraduate
    Wed, 24 Oct '18
  • University of Bradford
    Faculty of Health Studies Postgraduate
    Wed, 24 Oct '18
  • Northumbria University
    All faculties Undergraduate
    Wed, 24 Oct '18
Poll
Do protests make a difference in political decisions?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Equations

Best calculators for A level Maths

Tips on which model to get

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.