Algorithm Analysis (Big Theta)

[jhudson1]

Homework Statement

Here is a pastebin link to my question, it contains an algorithm, my trace of the algorithm, and my question.

Homework Equations

I am interested in the theta notation for the runtime of an algorithm

The Attempt at a Solution

Here is the link
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

 

[Dick]

Homework Statement

Here is a pastebin link to my question, it contains an algorithm, my trace of the algorithm, and my question.

Homework Equations

I am interested in the theta notation for the runtime of an algorithm

The Attempt at a Solution

Here is the link
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

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

 

[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

 

[Dick]

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

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.

 

[Dick]

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

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.