# Algorithm Analysis (Big Theta)

1. Nov 15, 2012

### jhudson1

1. The problem statement, all variables and given/known data
Here is a pastebin link to my question, it contains an algorithm, my trace of the algorithm, and my question.

2. Relevant equations
I am interested in the theta notation for the runtime of an algorithm

3. The attempt at a solution
http://mathb.in/1202

My thoughts are that the algorithm must run in either n^2 or n lg (n) where lg = log base 2

2. Nov 15, 2012

### Dick

Which of those choices do you think fits better? And why? Think about LARGE n.

3. Nov 15, 2012

### jhudson1

n^2 definitely.

I guess what threw me was the floor function. I wasn't sure if I could multiply through that or not and say n^2/2. Since it seems that you can, 1/2 is clearly scaling the order of the algorithm, which is n^2

4. Nov 15, 2012

### Dick

Sure. floor(i/2) isn't exactly i/2 but it's pretty close. On the other hand n*log(n) is clearly way off.

5. Nov 15, 2012

### Dick

Thinking about this a little more, isn't the more accurate estimate (1/4)*n^2? You don't just multiply but it's still basically n^2.