Computational complexity question

AI Thread Summary
The algorithm's computational complexity is represented by the expression $(N-1) + \sum_{i=1}^{N-3}(i+1)(N-2)!/{i!}$. In Big O Notation, this simplifies to O(n!), indicating factorial time complexity. The sum contributes significantly to the overall complexity, approximating to (n - 2)!. The coefficients in the sum are negligible, allowing for their exclusion in the final complexity assessment. The discussion confirms the accuracy of this representation.
pemfir
Messages
4
Reaction score
0
how can i represent the computational complexity an algorithm that requires the following number of operations: (please see attached document)

Code: 
$(N-1) + \sum_{i=1}^{N-3}(i+1)(N-2)!/{i!}$
 

Attachments

  • computational complexity.JPG
    computational complexity.JPG
    1.9 KB · Views: 425
Mathematics news on Phys.org
In Big O Notation, that would be simply O(n!) I believe, factorial time. The sum group amounts to (n - 2)! with a coefficient 2 + 1.5 + 0.6666 +... which is discarded (so is the -2), and the n - 1 grows so slow relative to the rest that it can be discarded to.
 
thank you very much you are precisely correct
 

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Thread 'Fermat's Last Theorem'

Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
View full post »
Thread 'Imaginary Pythagorus'

Thread 'Imaginary Pythagorus'

I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
View full post »

Similar threads

A Are these two optimization problems equivalent?
Replies
1
Views
1K
B Are Inverse Problems More Complex Than Direct Problems in Mathematics?
Replies
13
Views
3K
A Expansion with respect to ##z_1##
Replies
1
Views
1K
MHB Math Help: Understand How to Compute $F_{X_1}(x)$
Replies
1
Views
1K
B How does the Riemann Hypothesis/Riemann Zeta function even work?
Replies
17
Views
866
I How to do algebra on the Kitaev toric code grid?
Replies
18
Views
2K
I Modulo and Modulus in math and computer programming
Replies
5
Views
3K
B Computing a tricky complex math problem - where did I go wrong?
Replies
7
Views
1K
Insights Views On Complex Numbers
3
Replies
108
Views
10K
MHB Compute $\sum_{n=1}^{2020} (f(n)-g(n))$
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top