You are Here: Home >< Maths

# Big O notation: recurrence relation watch

1. 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

Can I then simplify the second one to
?
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?
2. I don't see an issue with removing constant factors here. (Doesn't mean I'm not missing something, of course).
3. Ok then, final answers I get

?
So that would mean that b is more efficient I believe.

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 , we can expand

Applying the same theory again -

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

From this, we can deduce (i.e. spot the pattern) the relation

If we let n = 1

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 . I have skipped steps in this one, but the theory is the same.

Again, by deduction

is larger than 2, and is therefore asymptotically larger than n^2. is therefore the more efficient as it is O(n^2) vs O(n^2andabit).
5. (Original post by Chrosson)
x
I think I can follow that, thanks . Though, why are we substituting n for 3n, and then 9n? Are those arbitrary choices or do they come from somewhere?
6. (Original post by secretmessages)
I think I can follow that, thanks . 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.
7. I disagree with your conclusion.

Spoiler:
Show
Suppose

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?
8. (Original post by DFranklin)

Spoiler:
Show
Suppose

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
9. (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
10. (Original post by DFranklin)

Spoiler:
Show
Suppose

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 . I'll have to check tomorrow. Too late now.
Also, the latex limit is kinda irritating.

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: January 14, 2010
Today on TSR

### Summer Bucket List is Back!

Start yours and you could win £150!

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams