/prog/ - Complexity

Name: Anonymous 2012-11-12 16:01

If a recursive algorithm calls itself twice for each element in a set, does that mean it has n^2 complexity, or is that 2n and therefore n complexity? I am confused.

Name: Anonymous 2012-11-12 16:11

>>1
that would depend on the algorithm (you haven't stated even the base condition

Name: Anonymous 2012-11-12 17:12

Depends how the size of the set the algorithm works on reduces every time it calls itself.
The simplest case of O(n²) that I can think of is for (i in set) { for (j in set) { do a thing } }, but that's not recursive.

Is there any recursive O(n²) algorithm? On a minute of thinking, I don't see how there could be one that isn't on the logarithmic scale.

Name: Anonymous 2012-11-12 17:34

>>3
shalom, hymie!

Name: Anonymous 2012-11-12 17:51

>>4
where is latest version of symta?

Name: Anonymous 2012-11-12 17:58

#lang racket

(define (all-pairs s)

    (if (<= (length s) 1) '()

        (append (map (λ(x)(cons (car s) x))

                     (cdr s))

                (all-pairs (cdr s)))))

Name: Anonymous 2012-11-12 18:21

>>3
>>6 is surely not on the log scale.

Name: Anonymous 2012-11-12 21:31

In J, the adverbial train "0/~ applies a verb to all pairs of a set.

Name: Anonymous 2012-11-12 23:04

>>8
too bad the ``documentation'' is retarded as fuck.

Name: niggtg 2012-11-13 0:08

>>3
Are you retarded? any iterative program can be written recursively, so of course there are.

Name: Anonymous 2012-11-13 0:14

complex dubs

Name: 2012-11-13 3:36

Name: Anonymous 2012-11-13 8:34

>>2
tfw no one takes the only true statement seriously

Name: Anonymous 2012-11-13 13:45

/polecat kebabs/

Complexity

1 Name: Anonymous 2012-11-12 16:01

2 Name: Anonymous 2012-11-12 16:11

3 Name: Anonymous 2012-11-12 17:12

4 Name: Anonymous 2012-11-12 17:34

5 Name: Anonymous 2012-11-12 17:51

6 Name: Anonymous 2012-11-12 17:58

7 Name: Anonymous 2012-11-12 18:21

8 Name: Anonymous 2012-11-12 21:31

9 Name: Anonymous 2012-11-12 23:04

10 Name: niggtg 2012-11-13 0:08

11 Name: Anonymous 2012-11-13 0:14

12 Name: 2012-11-13 3:36

13 Name: Anonymous 2012-11-13 8:34

14 Name: Anonymous 2012-11-13 13:45