0

I am doing a research in my class on algorithms complexities , I need to know if there is any other complexities of algorithms , what I know and studied is 2 types 1- is the in the BIG O complexity that is time and performance and other 2- is the space complexity that is the memory complexity , do algorithms have any other kind of complexities? Is algorithms measured by anything else that I miss?

unwind
  • 391,730
  • 64
  • 469
  • 606
user1760556
  • 489
  • 1
  • 4
  • 4

1 Answers1

5

In terms of asymptotical complexity of algorithms - yes, algorithms (and problems) are measured in terms of space and time.

However, there is a lot more I can say about it. I'll try to address some issues:

Space/time consumption is derived from a method of analysis
There are 4 common methods of analysis for algorithms, used for both space and time. Remember that big-O is a set of functions, but how do you derive the function? The function of the complexity is derived according to the method of analysis, which is (usually) one of the following:

Each one of these methods can be used on any algorithm - and the results aren't guaranteed to be the same. For example, quick sort has O(n^2) worst case time complexity and O(nlogn) average case time complexity.

More sets:
In addition to big O notation, we also use other notation to denote the complexity. Additional common notations are (by commonality of usage):

  • Big Theta (Θ)
  • Big Omega (Ω)
  • Small o
  • Small omega (ω)

Not to be confused with the methods of analysis: Each of Big Theta/Big O/ notations... can be paired with any analysis method (worst case/average case/...)
More details on Big Theta, Big O and the differences between them can be found in this thread

Theoretical Complexity:
In the field of theoretical "Complexity Theory" - we analyze problems, not algorithms. In this field, we care if a problem can be solved polynomially (that is, if the input is of size n, then the problem can be solved in some power of n), verified polynomially (given a possible solution, check if it is correct). However, there are other classes as well.
The common complexity classes are:

In addition - we are interested if problems are solvable/decidable at all. Common classes for describing the solvability of problems are:

Real world:
In real world apps - we care not only about the theoretical space/time complexities, but also about the constants (an algorithm that takes half the time as another is much better, even though they can be in the same complexity class. This is because complexity classes ignore constants.).
We also consider implementation time and maintainability of the program/algorithm.

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • thanks that seems clear and perfect can you plz let me know if there is a list of algothims with there complexities space and time if you do not have soemthing in mind no worries – user1760556 Oct 22 '12 at 10:37
  • Have a look on [List of algorithms in wikipedia](http://en.wikipedia.org/wiki/List_of_algorithms). Almost all algorithms have their complexity in their pages. – amit Oct 22 '12 at 10:39
  • @GregRos: Thanks for the edit. The answer is much more understandable now. You have done a great job reviewing my English - thank you for that. – amit Oct 23 '12 at 22:08
  • Oh, sure. :) I hope I managed to leave the meaning as-is. It's a very informative answer, the kind you seldom see. – GregRos Oct 24 '12 at 16:01