Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

CS

Name: Anonymous 2012-09-24 23:33

How can i into Algorithm complexity analysis?

example:
How do i formally prove that the Binary Search is O(log(n)) on sorted arrays?

How fib(n) solved in a naive recursive way is O(2n])?

Mathematically that's

Name: Anonymous 2012-09-25 20:52

>>40
that's genius, has anyone tried to implement it yet?

Name: Anonymous 2012-09-25 21:00

>>39
Bleh you're boring. Try this instead:

let rec foo x y = match (x, y) with
| (0, _) -> y + 1
| (_, 1) -> foo (x - 1) 1
| (_, _) -> foo (x - 1) (foo x (y - 1));;

Name: Anonymous 2012-09-25 21:03

>>34
I'm childish now for making a suggestion? Did I ever said he was an useless piece of shit? No, I told him his post was useful and how he *should* drop the tripcode, that's all.

Name: Anonymous 2012-09-25 21:14

>>43
The way you made the "suggestion" (repeated demand) was childish, but not quite as childish as just about everything else you said. If anything, you should go elsewhere and tripfag-sama should stick around.

CBF to care either way though.

Name: Anonymous 2012-09-25 21:20

>>44
I don't care if he stays, he's not shitposting.

The ``repeated demand'' part was just myself justifying my suggestion.

For now, I should stop shitting up the thread.

Name: Anonymous 2012-09-25 21:21

>>40
>Every number can be mapped 1:1 to positive unsigned integer(representing the number itself)
stopped reading there

Name: Anonymous 2012-09-25 21:24

>>46
learn how to quote onegai

Name: Anonymous 2012-09-25 21:32

his is my site wide tripcode. I use it for a variety of reasons that happen to not include shittposting and posting for attention.
Ooh, are they, "I wanted to re-find my posts easily," and, "I wanted to more accountable so I make higher quality posts"?

Name: Anonymous 2012-09-25 21:40

>>40
Alright how many drugs must I take before that makes sense? Also, can you give me a TL;dr of what it actually does?

Name: Anonymous 2012-09-25 21:45

>>47
I think you'd be better off using kudasai.
/autism

Name: Anonymous 2012-09-25 21:45

>>39

T(1) = 1
T(N) = T(N-1)+T(N-2)+T(N-3)+...+T(1)+1
when you try simple substitution you should realize a pattern that only the functions to the left can spawn (1) function seen to the right. i.e: T(N) can only spawn 1 T(N-1) call; therefore, we can start to notice that the coefficients of each call T(M) for some M < N should be 2(N-M-1). i.e: N = 5, M = 4 T(4) coefficient should be 25-4-1 = 1


T(N) = (2(1-1))T(N-1) + (2(2-1))T(N-2) + ... + (2((N-1)-1)T(1) + 1
simplifing T(1) coefficient
T(N) = (2(1-1))T(N-1) + (2(2-1))T(N-2) + ... + (2(N-2)T(1) + 1
T(N) = (1)T(N-1) + (2)T(N-2) + ... + (2(N-2))T(1) + 1
Since the coefficient equates to the number of times we'll call T with argument M for some integer we can see that this is a simple series:
   
   /  (n-1)        \
  |   ____          |
  |   \             |
  |   /___   2(x-1)  / + 1     = total number of calls for Input N
   \    1          /

Using some math, you should be able to reason the series to become simply:
  (2(n-1)-1)+1
=> 2(n-1)

Therefore: O(2(n-1))


is that a good enough proof or am i doing it wrong?

Name: Anonymous 2012-09-26 4:54

>>41
IHBT, except that isn't the original thread.
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -