For those familiar with algorithmic complexity

[Mavrick]

I had a test today where I had to find the algorithmic complexity (Big-Oh notation) for a time equation.

T(n) = T(n-2) +1

Well, I would like to know if somebody knows the compexity of this algorithm (so I can know if me or my friends are right

We had 3 different answer : O(n), O(logn), O(2^n)

So if you know well how to do these, feel free to give a though

 

[Mavrick]

Bump...

 

[phobinator]

Just had this class about a year ago, these are easy because there are theorems you can follow based on the structure of the equation.

In this case, its T(n) is theta(N^k+1) using the format T(n) = T(n-1) + theta(n^k).

I think the answer is theta(n) or theta(n^(0+1))- or for what your asking- (the upper bound) T(n) is still O(n)

 

[gopunk]

it is O(n)

 

[Mavrick]

Yeah, that's also what I though...
The problem is... under stress, I wrote O(log n)....

 

[gopunk]

that sucks....

the way i have been told to do it (in a class that is *not* specifically about algorithmic complexity) is to ignore any numbers multiplying/dividing or adding/subtracting. because those are just constants. perhaps this is a wrong method, but i haven't been wrong yet

 

[Ameesh]

oops i should read more carefully

 

[Ameesh]

Originally posted by: gopunk
that sucks....

the way i have been told to do it (in a class that is *not* specifically about algorithmic complexity) is to ignore any numbers multiplying/dividing or adding/subtracting. because those are just constants. perhaps this is a wrong method, but i haven't been wrong yet

sounds about right as long as you dont have recursive defintions and your only solving for big-O

 

[Mavrick]

I know it's stupid. It's just that under stress, I figured out that this is a recursive call, and since each call reduce the size of the problem by 2, the complexity would be logarithmic... (well, it is like that, but only if the size is DIVIDED by something, not just a substraction...

At least, I did figure it out!!! And I have not written O(2^n) like a lot of people I know!!!

 

[Ameesh]

Originally posted by: Ameesh

Originally posted by: gopunk
that sucks....

the way i have been told to do it (in a class that is *not* specifically about algorithmic complexity) is to ignore any numbers multiplying/dividing or adding/subtracting. because those are just constants. perhaps this is a wrong method, but i haven't been wrong yet

sounds about right as long as you dont have recursive defintions and your only solving for big-O

oh and the adding, subtracting, division, and multiplaction must be with constants.

 

[RichieZ]

all i have to say is BigO notation SUX!