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

FAQ: Computational complexity question

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?
Replies
1
Views
1K
B Are Inverse Problems More Complex Than Direct Problems in Mathematics?
Replies
13
Views
2K
MHB Math Help: Understand How to Compute $F_{X_1}(x)$
Replies
1
Views
844
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
2K
B Computing a tricky complex math problem - where did I go wrong?
Replies
7
Views
1K
MHB Compute $\sum_{n=1}^{2020} (f(n)-g(n))$
Replies
1
Views
848
A How to sum an infinite convergent series that has a term from the end
Replies
15
Views
2K
I Newton-Raphson Method With Complex Numbers
Replies
7
Views
2K
I Formal definition of multiplication for real and complex numbers
Replies
2
Views
979

Hot Threads

Recent Insights

Back
Top