The discussion revolves around analyzing the runtime of an algorithm using Big Theta notation. Participants are examining the potential growth rates of the algorithm, specifically considering whether it operates in Θ(n²) or Θ(n log n) as n approaches large values.
Several participants express a strong inclination towards Θ(n²) as the appropriate classification for the algorithm's runtime. There is ongoing exploration of how the floor function influences this classification, with some suggesting that it could lead to a more precise estimate of (1/4)n². However, there is no explicit consensus on the final classification.
Participants are working from a shared link containing the algorithm and its trace, which may be influencing their interpretations. The discussion is framed around large values of n, which is a critical aspect of their analysis.
jhudson1 said: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
jhudson1 said: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
jhudson1 said: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