Computational complexity question

Click For Summary
SUMMARY

The discussion centers on representing the computational complexity of an algorithm with a specific operation count, expressed as $(N-1) + \sum_{i=1}^{N-3}(i+1)(N-2)!/{i!}$. The consensus is that this complexity can be simplified to Big O notation as O(n!), indicating factorial time complexity. The contributors agree that the sum converges to (n - 2)!, and the linear term (N-1) is negligible in comparison to the factorial growth.

PREREQUISITES
  • Understanding of Big O Notation
  • Familiarity with factorial functions
  • Knowledge of summation notation
  • Basic algorithm analysis skills
NEXT STEPS
  • Study the implications of O(n!) complexity on algorithm performance
  • Explore advanced summation techniques in algorithm analysis
  • Learn about other factorial time complexities and their applications
  • Investigate optimization strategies for algorithms with high computational complexity
USEFUL FOR

Computer scientists, algorithm designers, and students studying computational complexity who seek to deepen their understanding of factorial time complexities and their implications in algorithm performance.

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: 445
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
 

Similar threads

Graduate Are these two optimization problems equivalent?
  • · Replies 1 ·
Replies
1
Views
2K
High School Are Inverse Problems More Complex Than Direct Problems in Mathematics?
  • · Replies 13 ·
Replies
13
Views
3K
MHB 1.4.1 complex number by condition
  • · Replies 13 ·
Replies
13
Views
2K
Graduate Proving Goldbach's conjecture by induction (or why it doesn't seem to work)
  • · Replies 10 ·
Replies
10
Views
3K
Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
1K
High School Looking for context for a textbook quote
  • · Replies 9 ·
Replies
9
Views
2K
Undergrad What is Integer Complexity and Why Does It Matter?
  • · Replies 12 ·
Replies
12
Views
2K
Insights The History and Importance of the Riemann Hypothesis
  • · Replies 0 ·
Replies
0
Views
3K
High School Imaginary Pythagoras
  • · Replies 13 ·
Replies
13
Views
2K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
3K