/prog/ - Program to find Big-O notation?

Name: Anonymous 2013-06-17 23:43

Is there a program or a library that I could use to find the O() of an algorithm? For example,



def O_1(n):

    return n



def O_n(n):

    s = 0

    for i in range(0, n):

        s = s + i

    return s

    

def O_n2(n):

    m = 1

    for i in range(1, n + 1):

        for j in range(1, n + 1):

            m = m * i * j

    return m

    

print("O(O_1()) = "  + O(O_1) ) # O(O_1()) = O(1)

print("O(O_n()) = "  + O(O_n) ) # O(O_n()) = O(n)

print("O(O_n2()) = " + O(O_n2) ) # O(O_n2()) = O(n^2)

Is there a library that would work as O(f) should?

Name: Anonymous 2013-06-17 23:44

le egin notation le muh algoritumz speed xd xd el computer science

Name: Anonymous 2013-06-17 23:47

The point of Big-O is that you do not run the program
please read Algorithms 4th edition by swedgewick
or the first volume of the Art of Computer Programming

Name: Anonymous 2013-06-17 23:53

الله أكبر

Name: Anonymous 2013-06-18 0:05

Motion to make Big O a /prog/-approved anime.

Name: Anonymous 2013-06-18 0:06

Motion to ban all anime from /porg/.

Name: Anonymous 2013-06-18 0:06

>>5
Aye.

Name: Anonymous 2013-06-18 0:19

Yeah, you can probably grab Coq and use it to help with analysis.

Name: Anonymous 2013-06-18 0:26

LLLLLLLEEEEEEEEEEEEEEEEEEELLLLLLLLLLLLL
>he said to grab cock

Name: Anonymous 2013-06-18 0:35

Motion to suck my cock.

Name: Anonymous 2013-06-18 1:15

>>1
I strongly suspect that such a library is provably impossible in the general case, since such a library could be trivially used to solve the halting problem. If you don't have access to the source, the best approach would be to just rig up a test harness of varying input sizes and see how average response time varies. Of course, that's horribly inaccurate, and if you have access to the source at all what you should really do is just follow >>3 's instructions andtake the analysis yourself, which will save you from the O(1000n + 0.001n^2) case.

Name: Anonymous 2013-06-18 1:16

Coq n-balls.

Name: Anonymous 2013-06-18 1:39

i bet it's possible to write such library for the MASTER THEOREM

Name: Anonymous 2013-06-18 2:09

reduces to da halting problem yo. so no not in general. however you can still make one for a restricted class of algorithms.

Name: Anonymous 2013-06-18 2:38

I'm sick of this `halting problem' shit. If so many things being solved would solve the problem, then there are lots of places to attack and it would be solved by now.

Name: Anonymous 2013-06-18 3:01

>>15
solving the halting problem is a logical paradox.

Name: Anonymous 2013-06-18 3:59

>>13
As a black mathematician, I am offended by that.

Name: Anonymous 2013-06-18 4:14

>>16
because it involves infinity which is kike bullshit

Name: Anonymous 2013-06-18 6:47

>>18
illogical finitist cretin

Name: Anonymous 2013-06-18 6:49

>>5
it's showtime

Name: Anonymous 2013-06-18 6:52

>>5
What is the time complexity of a Perl regex?

Name: Anonymous 2013-06-18 6:56

>>19
How is believing in some nonexistent "infinity" more logical than not believing in it? Does "infinity" answer your prayers? Does it perform miracles and heal the mutilated? Have you seen any signs of "infinity" that changed your life?

Name: Anonymous 2013-06-18 7:01

>>22
infinity just blew me (shit was SO cash)

Name: [kike] 2013-06-18 7:02

>>23

Name: Anonymous 2013-06-18 7:03

>>24
A fatal error occured!

You didn't write a post?!

Name: [kike] 2013-06-18 7:05

>>23
Shalom, Solomon!

Name: Anonymous 2013-06-18 7:06

>>26
Peace, Stud!

Name: Anonymous 2013-06-18 18:42

You know what's more illogical than infinity? Retards who are willing to claim that arithmetic simply breaks down after a while and throw out all what calculus and algebra allows for ideological purity. And if you seriously believe clock arithmetic is the answer, you need to kill yourself. There is absolutely no reason to suppose that that is the case except a blind refusal to accept simple logical deductions in number theory and set theory.

Name: Anonymous 2013-06-18 20:55

>>28
the halting problem proof is a bit odd, you have to admit

Program to find Big-O notation?

1 Name: Anonymous 2013-06-17 23:43

2 Name: Anonymous 2013-06-17 23:44

3 Name: Anonymous 2013-06-17 23:47

4 Name: Anonymous 2013-06-17 23:53

5 Name: Anonymous 2013-06-18 0:05

6 Name: Anonymous 2013-06-18 0:06

7 Name: Anonymous 2013-06-18 0:06

8 Name: Anonymous 2013-06-18 0:19

9 Name: Anonymous 2013-06-18 0:26

10 Name: Anonymous 2013-06-18 0:35

11 Name: Anonymous 2013-06-18 1:15

12 Name: Anonymous 2013-06-18 1:16

13 Name: Anonymous 2013-06-18 1:39

14 Name: Anonymous 2013-06-18 2:09

15 Name: Anonymous 2013-06-18 2:38

16 Name: Anonymous 2013-06-18 3:01

17 Name: Anonymous 2013-06-18 3:59

18 Name: Anonymous 2013-06-18 4:14

19 Name: Anonymous 2013-06-18 6:47

20 Name: Anonymous 2013-06-18 6:49

21 Name: Anonymous 2013-06-18 6:52

22 Name: Anonymous 2013-06-18 6:56

23 Name: Anonymous 2013-06-18 7:01

24 Name: [kike] 2013-06-18 7:02

25 Name: Anonymous 2013-06-18 7:03

26 Name: [kike] 2013-06-18 7:05

27 Name: Anonymous 2013-06-18 7:06

28 Name: Anonymous 2013-06-18 18:42

29 Name: Anonymous 2013-06-18 20:55

Name: Anonymous 2013-06-17 23:43

Name: Anonymous 2013-06-17 23:44

Name: Anonymous 2013-06-17 23:47

Name: Anonymous 2013-06-17 23:53

Name: Anonymous 2013-06-18 0:05

Name: Anonymous 2013-06-18 0:06

Name: Anonymous 2013-06-18 0:06

Name: Anonymous 2013-06-18 0:19

Name: Anonymous 2013-06-18 0:26

Name: Anonymous 2013-06-18 0:35

Name: Anonymous 2013-06-18 1:15

Name: Anonymous 2013-06-18 1:16

Name: Anonymous 2013-06-18 1:39

Name: Anonymous 2013-06-18 2:09

Name: Anonymous 2013-06-18 2:38

Name: Anonymous 2013-06-18 3:01

Name: Anonymous 2013-06-18 3:59

Name: Anonymous 2013-06-18 4:14

Name: Anonymous 2013-06-18 6:47

Name: Anonymous 2013-06-18 6:49

Name: Anonymous 2013-06-18 6:52

Name: Anonymous 2013-06-18 6:56

Name: Anonymous 2013-06-18 7:01

Name: [kike] 2013-06-18 7:02

Name: Anonymous 2013-06-18 7:03

Name: [kike] 2013-06-18 7:05

Name: Anonymous 2013-06-18 7:06

Name: Anonymous 2013-06-18 18:42

Name: Anonymous 2013-06-18 20:55