What is Complexity: Definition and 147 Discussions

Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, meaning there is no reasonable higher instruction to define the various possible interactions.The term is generally used to characterize something with many parts where those parts interact with each other in multiple ways, culminating in a higher order of emergence greater than the sum of its parts. The study of these complex linkages at various scales is the main goal of complex systems theory.
Science as of 2010 takes a number of approaches to characterizing complexity; Zayed et al.
reflect many of these. Neil Johnson states that "even among scientists, there is no unique definition of complexity – and the scientific notion has traditionally been conveyed using particular examples..." Ultimately Johnson adopts the definition of "complexity science" as "the study of the phenomena which emerge from a collection of interacting objects".

View More On Wikipedia.org
Recent contents Top users
  1. evinda

    MHB Algorithm with time complexity o(n^2)

    Hi! (Smile) I am looking at the following exercise: Let $M=\{ y_1, y_2, \dots, y_n \}$ a set of real numbers, where $n \geq 2$. Describe an algorithm, that has time complexity $o(n^2)$ and that finds and returns two elements $y_k$ and $y_l$ of $M$, such that: $$|y_k-y_l|=\min_{1 \leq i,j \leq...
  2. evinda

    MHB Creating List $L_3$ from $L_1,L_2$ w/ $O(n_1+n_2)$ Complexity

    Hello! (Wave) Given two lists, $L_1$ with $n_1$ elements and $L_2$ with $n_2$ elements, I want to write an algorithm that creates a new list $L_3$, for which the following stand: The elements at the odd positions of $L_3$ are these that are at the even positions of $L_1$ The elements at the...
  3. evinda

    MHB Exploring Static Queue Operations and Complexity

    Hi! (Wave) I am looking at the operations of a static queue. pointer MakeEmptyQueue(void) pointer Q; /* temporary pointer */ Q = NewCell(Queue); /* malloc() */ Q->Front = 0; Q->Length = 0; return Q; I have to find the complexity of the above...
  4. M

    MHB What Are the Focus Areas in the Course Algorithms and Complexity?

    Hey! :o I take the course Algorithm and Complexity and I have to choose one of the fields Computer Science(the operations of a computer), Computational Geometry or Cryptography. Could you give some information about these fields?? (Wondering)
  5. evinda

    MHB Can we merge two unsorted lists in constant time?

    Hello! (Wave) I want to write an algorithm, that merges two unsorted lists and returns a pointer to the first list, that should then contain both the elements of the first and the second list. The algorithm should have a constant time complexity. To do that, shouldn't we traverse the first...
  6. evinda

    MHB What is the time complexity of the binary search algorithm?

    Hello! (Wave) Index BinarySearch(Type A[1...N], Type value, Index low, Index high){ 1. Index mid; 2. if (high<low) 3. return -1 4. mid=low+(high-low)/2; 5. if (A[mid]>value) 6. return BinarySearch(A, value, low,mid-1); 7. else if (A[mid]<value)...
  7. evinda

    MHB Finding the asymptotic complexity of a function

    Hello! (Wave) I want to find the asymptotic complexity of the function: $$g(n)=n^6-4n^5 \log^2 n-10-5n^3$$
  8. evinda

    MHB Analyzing Time Complexity and Memory of Binary Search Algorithm

    Hello! (Wave) I want to show that the $T(n)$ of the following algorithm is equal to $O(\log n)$. How can we do it, now that we have if, else conditions? (Thinking) int BinarySearch(int A[1…n], int y, int low, int high) { if (high < low) { return -1; //not found } mid = low + (high -...
  9. gfd43tg

    What Determines the Asymptotic Time Complexity of T(n)=n^2+3?

    Homework Statement In this question you will determine the asymptotic time complexity of an algorithm for which the complexity is ##T(n)=n^{2}+3##. Find a positive real c and a positive integer ##k##, such that ##T(n) \le cf(n)## holds for all ## n>k ## if ##f(n) ## is the asymptotic time...
  10. A

    Learning Vectors in Physics: How Complex is it?

    I am currently learning vectors in physics. Things such as adding, subtracting, multiplying and converting between polar and Cartesian. I was just wondering how complex this concept really is. I am completely confused when I look at it but when the teacher tries to explain it I feel like it's an...
  11. Y

    Physics Major Questions: Should I Change Majors?

    Hello. I am currently a physics major and in my sophomore year at UT Austin. I have always been interested in physics, specifically astrophysics. But I have recently become discouraged. Not because of the rigor of physics but more because of the way it is taught and also what seems to me to be...
  12. K

    MHB Exact inversion of matrix complexity (by Gaussian elimination)

    I would like to check if what I have done is correct. Please, any input is appreciated. **Problem statement:** Consider a non-singular matrix $A_{nxn}$. Construct an algorithm using Gaussian elimination to find $A^{-1}$. Provide the operation counts for this algorithm. **My attempted algorithm...
  13. D

    Find Direct Common Tangent of 2 Circles without Complexity

    Homework Statement Is there any direct formula for calculating the direct common tangent of two circles without having to go all the trouble of using y-y1=m(x1-x2) to derive it for two separate tangents t1 and t2. If there is could anyone explain to me how it is derived? Homework...
  14. G

    Asymptotic time complexity of Recursive function

    Homework Statement I've been asked to develop a recursive function and then analyze the asymptotic time complexity. f(N) = 0, if N < N1 f(N1) = C1 f(N)= A1 + M1*f(M2*N/D1 - S1) Op M3*f(M4*N/D2 - S2), if N > N1 Homework Equations We're to assume that: s1 = s2 = 0 m2 =...
  15. R

    Why is the complexity of this code O(n^2)?

    def fib(n): f0, f1, = 0, 1 for i in range(n - 1): f0, f1 = f1, f0 + f1 return f1 It looks like it'd be linear, given there's only one loop, but when I plotted n against runtime, the relationship was quadratic, why?
  16. C

    Complexity of irrationals

    How would I figure out the Kolmogorov complexity of an irrational number? Could I just look at the shortest formula to compute that number. If it is an uncomputable real, does it have infinite complexity?
  17. M

    MHB Improvement algorithm and its time complexity

    Hi, I have a problem with the following problem: Assume fj is concave and strictly increasing for all j, j=1,..,n. Show that the optimal solution x* satisfies the condition (from j=1 to n) ∑x*j=B. Now consider the following improvement algorithm: start with x0=0 for k=1:B select...
  18. P

    Help finding Complexity in Big-O notation

    Homework Statement I have found the complexity of an algorithm as the expression below. How can I find the complexity in big O notation for such expression? Or proved that it's bounded by n^3 or n^4 ? Thank you! Homework Equations \sum_{j=3}^{n} \left[(j-1)[2(j-2)-1] +...
  19. P

    Computational complexity question

    how can i represent the computational complexity an algorithm that requires the following number of operations: (please see attached document) $(N-1) + \sum_{i=1}^{N-3}(i+1)(N-2)!/{i!}$
  20. S

    Complexity of a quadratic program

    I'm trying to compute the complexity of the quadratic program: $$\displaystyle\min_{\mathbf{X}} (\mathbf{X^TQX +C^TX}) \quad{} \text{subject to} \quad{} \mathbf{A X \leq Y}$$ A is MxN and X is Nx1. Q is positive definite and I'm using the interior point method. Any help in computing the...
  21. B

    Do circuits have complexity classes?

    In the field of computer science, algorithms are often assigned a "complexity" class that is a measure of the time complexity of an algorithm. An algorithm with higher time complexity can take longer to compute than one with less time complexity. I was wondering if circuits also have a...
  22. F

    Java Trying to come up with simple algorithm of significant time complexity in Java

    Hi PF, I'm working on a program that requires measuring how long it takes a given computer to process a certain task, but am having trouble coming up with algorithms that won't take most computers a trivial amount of time to perform. The only one I've got so far is recursively computing...
  23. mrspeedybob

    Uncovering the Complexity of Single Neurons: A Look into Homoclinic Orbits

    A brief internet search revealed that the number of neurons in a human brain is in the 85 - 100 billion ballpark. (reference) What I could not find was any clear indication of how complex a single neuron is. Is the brain like a network of 85 - 100 billion transistors or 85 - 100 billion...
  24. G

    Why is the universe so complex?

    Lately i have been wondering why the universe is so complex. I cannot comprehend how something that is said to be arbitrary can be so uniformly perfect,from perspective, I hate that I have no free will or i assume I do not, nor can I comprehend the meaning of anything.I think I am having an...
  25. A

    Complexity Big O, little o

    Hi When we have f(n) \in o(g(n)) and g(n) \in O(H(n)) Can I proove that h(n)-f(n) \in o(g(n))? Obviously I don't want you to give me the answer, but some hints and maybe which definitions of O and o I should use. Thanks
  26. B

    Lyndon words: Duval's algorithm and its time complexity

    Hi everyone, Duval' algorithm computes all the k-ary Lyndon words up to any length, say n. See here for a brief introduction to Lyndon words and note the section Generation. http://en.wikipedia.org/wiki/Lyndon_word The article claims that "the sequence of all Lyndon words of length at most...
  27. I

    Questions about quantum mechanics reducing the complexity of classical models

    I have some questions about this paper: http://arxiv.org/abs/1102.1994v2 The author computes the entropy of the classical simulator using the Shannon entropy, then computes the entropy of the quantum simulator using von Neumann entropy and gets a smaller number, thus concluding that quantum...
  28. D

    Time complexity of matrix multiplications?

    Let A and B be n×n matrices, and let v be a column vector of length n. Which of the following two expressions is faster to compute? 1. ( A⋅ B )⋅ v or 2. A⋅ (B⋅ v) As a function of n, give the number of multiplications and additions required for each part. My attempt: So, I said that (2)...
  29. Z

    Algorithm Complexity how do I tell

    Hi, If the algorithm recurrence can be shown to belong to something complicated say like T(n) = log_{3/2} n lg(n) + (log_{3/2}(n) (log_{3/2}(n) - 1 ) /2) lg(2/3) What order of complexity can I expect it to be in?
  30. S

    Algorithm Complexity: Sorted Arrays into Sorted Array

    Homework Statement We have k >= 1 sorted arrays, each one containing n >= 1 elements (all equal length). We want to combine all of them into a single sorted array with kn elements. We have a "naive" algorithm: merge the first two arrays, then merge the third array into the result, then merge...
  31. J

    (A+B+C ) ^ (X + Y + Z ) of arbitrary complexity

    This question relates mostly to computer sciences (my personal field of expertise), I am trying to find the method for breaking down large floating point (non integer) numbers into a series of integers (so that they can be stored easily), and completing a power operation over them. for example...
  32. L

    Complexity analysis of algorithms

    Homework Statement Hello everyone. I am trying to analyse the complexity of an image processing algorithm. I have only the basic block diagram of the algorithm and I am trying to perform the complexity block by block. However, I do not know how to start and would like someone to point me in...
  33. C

    MHB Complexity of Algorithm to calculate number of nodes in a binary tree

    I guess this is the first question on partly CS topic in this forum. But I think you guys will be able to help me. I have an algorithm which goes as follows: int CN(struct node *node) { if(node==null) return 0; return 1 + CN(node->left) +...
  34. C

    Complexity of SAT in First-order logic

    I have been thinking about this question for weeks and can't figure it out! I reckon it's decidable and in EXPTIME, but not sure how to prove this! Any help would be reallllly appreciated! (Note: the question is in the attachment) -Peter
  35. S

    Proofs by induction on immediate predecessors (well-formed formula complexity)

    Hi physics forum, I have no idea where to start with this: As far as I know the general pattern for this sort of proof is, 1) All atomic well-formed formulas (wffs) have some property P 2) From the assumption that immediate predecessors of any non-atomic wff A have P, so too does A...
  36. S

    Proofs by induction on immediate predecessors (well-formed formula complexity)

    Hi physics forum, I have no idea where to start with this: As far as I know the general pattern for this sort of proof is, 1) All atomic well-formed formulas (wffs) have some property P 2) From the assumption that immediate predecessors of any non-atomic wff A have P, so too does A...
  37. B

    Programs What degree should I get to study complexity?

    I want to study complexity and emergence, but I am not sure what degree I should get. I am a second year college biology student, but I feel like biology lacks the math needed to understand a lot of these concepts. I am now veering towards a math degree, but I have not taken enough math to know...
  38. A

    What Is the Correct Derivation of Binary Search Complexity?

    i found the recursive relation which is T(n) = 1 + t(n/2) after a couple of substitutions i found the pattern which is T(n) = 2i-1 + T(n/ 2i) i chose i = log2 n and then when i plugged it in i got T(n) - 2log2(n -1) + T(1) but doesn't the first part simplify to n-1? the complexity...
  39. Y

    Computational complexity with an epsilon

    What does that mean when there's an \epsilon in the complexity, such as O(n^{2+\epsilon}) for every \epsilon >0
  40. P

    Analyzing the time complexity of an algorithm

    Homework Statement Analyze the worst-case time complexity of the following algorithm, which finds the first term of a sequence of integers equal to some previous term. procedure find (a1, a2, a3,..., an: integers) location := 0 i := 2 while i ≤ n and location = 0 begin j := 1 while j < i...
  41. P

    How reason that an algorithm has n*logn time complexity?

    Some time ago I wrote an exam where I had to write a pseudocode to sort elemens in a list. I used a quicksort with the pivot in the middle and wrote that the algorithm has time complexity in best case O(n*logn) because it is a divide-and-conquer algorithm. That didn't satisfy my teacher and he...
  42. R

    Exploring the Complexity of Physics Models

    Are the mathematical models which describe the laws of physics considered simple or complex?
  43. G

    Find Complexity of S(n) = S(n-1) + n^2.5

    I need to do this problem but I get stuck halfway through, Homework Statement Find complexity of S(n) = S(n-1) + n^2.5 for n > 1 and where S(1) = 2 Homework Equations The Attempt at a Solution What I did so far.. S(n) = S(n-1) + n^2.5 S(n-1) = S(n-2) + (n-1)^2.5 S(n-2)...
  44. M

    Software Engineering - cyclomatic complexity

    Homework Statement http://img17.imageshack.us/img17/651/cyclomaticcomplexity.png Homework Equations Main problem on part (i), am i correct on constructing the flow graph? The If statement after process x makes me quite confused. The Attempt at a Solution...
  45. D

    Time complexity and induction problems

    Homework Statement 1. HOARE-PARTITION(A,p,r) rearrange the array A[p...r] into 2 (possibly empty) subarray A[p...q] and A[q+1...r], so that each element of A[p...q] is at most A[p], and each element of A[q+1...r] is at least A[p]. x<-A[p] i<-p-1 j<-r+1 while true...
  46. M

    Exploring the Complexity of 3D Space

    hi, why do we need to have additional complexity to 3D space? we know that space holds information. but I'm not aware of any information in the universe which is held by "time dimension".. isn't there only changing space and our brain does the "time job" with memorizing and sorting...
  47. D

    What is the Time Complexity of this Sorting Algorithm on an Array?

    Homework Statement Compute the time complexity of the following sorting algorithm on an array L[0..n-1] in terms of n. Basic Operation only includes comparison and swap. sort (L, n) { int i=0, j; while(i<n-1){ s = i ; j=i+1...
  48. U

    O(sin n), Ω(sin n), Θ(sin n) complexity

    Hello , Do you know examples of functions belonging crowds O(sin (n)), Ω (sin (n)), Θ (sin (n)) ?
  49. N

    Is Pi More Complex than E? Insights from Number Theory

    I was reading a book on number theory, and there was an interesting dicussion about pi and e. It state that it took about one third less time to compute e to 100,000 places when compare to pi. Additionally, it stated that no "simple" partial fraction (that is, one in which all numerators are...
  50. S

    What is the meaning of M(n) in algorithm complexity analysis?

    I'm trying to teach myself some algorithm complexity and I've run into a problem. I'm starting to understand about O and o notation and big theta notation. I've run into notations like O(n^2 M(n)). Does this mean that the complexity is n^2 times whatever M(n) means? (Natural next question) what...
Back
Top