Computational complexity question

In summary, computational complexity is a measure of the time and resources required to solve a problem using a computer. It is typically measured by the time and space (memory) required and can be represented using big O notation. Time and space complexity refer to the number of operations/steps and amount of memory/storage required, respectively, and are important factors in determining overall computational complexity. This can greatly impact the performance of real-world applications, but it can be improved by designing more efficient algorithms or optimizing existing ones.
  • #1
pemfir
4
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: 386
Mathematics news on Phys.org
  • #2
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.
 
  • #3
thank you very much you are precisely correct
 

1. What is computational complexity?

Computational complexity refers to the amount of time and resources required to solve a problem using a computer. It is a measure of the efficiency of an algorithm or solution.

2. How is computational complexity measured?

Computational complexity is typically measured by the time and space (memory) required to solve a problem. This is often represented using big O notation, which describes the growth rate of the time or space as the input size increases.

3. What is the difference between time and space complexity?

Time complexity refers to the number of operations or steps required to solve a problem, while space complexity refers to the amount of memory or storage required to solve a problem. Both are important factors in determining the overall computational complexity of an algorithm.

4. How does computational complexity impact real-world applications?

The computational complexity of an algorithm can greatly impact the performance of a real-world application. A more efficient algorithm will require less time and resources to solve a problem, making it more practical and cost-effective to use.

5. Can computational complexity be improved?

Yes, computational complexity can be improved by designing more efficient algorithms or by optimizing existing algorithms. This can involve reducing the number of steps required to solve a problem, or finding more efficient ways to use memory and resources.

Similar threads

A Are these two optimization problems equivalent?
    • General Math
Replies
1
Views
395
MHB Math Help: Understand How to Compute $F_{X_1}(x)$
    • General Math
Replies
1
Views
695
B Direct and inverse problems
    • General Math
Replies
13
Views
1K
I Modulo and Modulus in math and computer programming
    • General Math
Replies
5
Views
2K
I How to do algebra on the Kitaev toric code grid?
    • General Math
Replies
18
Views
1K
I Formal definition of multiplication for real and complex numbers
    • General Math
Replies
1
Views
203
A How to sum an infinite convergent series that has a term from the end
    • General Math
Replies
15
Views
2K
I Newton-Raphson Method With Complex Numbers
    • General Math
Replies
7
Views
1K
MHB Compute $\sum_{n=1}^{2020} (f(n)-g(n))$
    • General Math
Replies
1
Views
739
B Computing a tricky complex math problem - where did I go wrong?
    • General Math
Replies
7
Views
826

Hot Threads

Recent Insights

Back
Top