Complexity Definition and 129 Threads

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

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?

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

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

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?

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

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

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

Homework Statement An Integral : \int \frac{1}{x^n(1+x^n)^{1/n}} \;\mathrm{d}x} Homework Equations The Standard integrals. The Attempt at a Solution I'm aware that integrals like this become very easy after a clever substitution...but maybe I'm not that clever...

I've been reading most of the threads here in particle physics forum. Recently, I noted a couple of threads started by enotstrebor which were a bit impolitic. Nevertheless, they raised some issues which are similar to those I have myself with the Standard Model as well Quantum Mechanics in...

I'll try to be as abstract as possible, but where needed, I'll give some concrete examples. If you have any questions, please ask. Note, I'm doing this for my hobby, not for any sort of homework. I've only followed an introductory course on computational complexity, so I'll let that be my...

How to express 1+1=2 the most complicated way imaginable?

Ok, I am brand new at this so I am kind of confused how to figure this out. i \leftarrow n while i >= 1 j \leftarrow i while j <= n <body of the j loop>, needs (1) j \leftarrowj*2 end j while i \leftarrowi-1 end i while I know that with nested...

like for any algorithm? On wikipedia it lists for multiplication it's O(n^2) but some of them have decimals like O(5/2n^2.2342) or something so how would you determine that? Just use a computer and make a graph of input in bytes vs time in seconds and fit a curve to it? Like I understand for...

What are complexity classes (P, NP, etc) in terms of pure sets? ZFC, I mean.

Homework Statement Indefinite integral: e^(4x+(e^4x)) Homework Equations I'm thinking integration by parts, involving UV minus integral of Vdu The Attempt at a Solution So I saw that this can be split into two: e^(4x) times e^(e^4x)). The latter is a bit complicated. I...

Hello everybody, Let's say we want to compute sqrt(x), where x is an integer of n digits. Then what is the cost of the computation, in terms of big O notation and n? And a second question: what is the algorithm for finding the square root that is most commonly used in computers and...

Hi Guys, Is algorithmic complexity determined mostly for primality tests or on-to prime-generating functions? Say, I have the function, Floor[(n!)/(n+1)], and for every n it produces primes, would I have to use the trig definition of the floor function to determine the complexity of this...