Complexity Definition and 148 Threads

Hey! :o I want to write a function for the constitution of a star system "ss". The new star system contains an empty list of planetary system, that means that in the list of the planetary system exists only the sentinel node, and the empty tree of the free-floating planets (ffp). The new star...

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...

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...

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...

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)

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...

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)...

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

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 -...

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...

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...

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...

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...

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...

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 =...

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?

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?

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...

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] +...

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!}$

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...

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...

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...

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...

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...

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

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...

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...

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)...

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?

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...

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...

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...

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) +...

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

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...

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...

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...

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...

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

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...

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...

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

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)...

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...

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...

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...

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...

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

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...