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: 426
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 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »

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 »

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
924
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