CS

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(2^n])?

Mathematically that's

Read SICP.

ONE WORD: THE FORCED PROVING OF ABSTRACTE BULLSHITE, THREAD OVER.

1. you recursively halve your search space. QED.
2. you keep calculating the same shit over and over and over. QED.

IHBT

read Wikipedia faggot

>>1

say you have a piece of paper and a one inch marker. And say you want to compute ceiling(log_2(n)) where n is the length of the piece of paper in inches. How would you do it?

>>6
I would fold the paper such that its length is halved repeatedly until the one inch marker is longer. The number of folds is the result.

>>7
now how do you perform binary search. Notice any similarities?

>>8
Of course I do. I understand the basics of complexity analysis because I'm not a baka like 1.

Read Sipser, CLRS, and SCIP.

>>3 is an idiot who can't into theoretical CS

To prove the time efficiency of an algorithm, break it up into pseudo code or a very high level approach which is even better.

For worst time complexity, give an argument about the worse case senario. Try to break your argument in a way that is generalized for the algorithm. If you're really formal, talk about loop invariants (google it or read CLRS). Ultimately you'll be talking about loops and loop depth, and the complexity of the inner most loop. i.e. it is easy to show that bubble sort is O(n^2) because it has a double for loop and the inside operation is constant time. If your algorithm calls other algorithms, it is necessary and sufficient to simply treat it as a black box, and refer to it's operational cost via it's time complexity.

For example:

We define BINARY SEARCH to take array A, and element X, and return the position of X in A, and -1 if not found.

Main loop: Compute the floor of A.length / 2 and call the element there Y.

 - If X = Y, return the position of Y
 - If A.length = 0, return -1
 - If X > Y, set A = A[ceiling(A.length/2) -> A.length]
 - Else if X < Y, set A = A[0 -> floor(A.length / 2)]
 - return to the main loop.

Correctness:

Here you show that for X not in A, BINARY SEARCH will terminate and return -1, and for X in A, BINARY SEARCH will terminate and return the right element. You have to include this step in a formal proof, other wise your algorithm could be something along the lines of compute O(log(n)), sleep, O(log(n)), and return 0, and you'd be able to prove the time complexity, but it wouldn't mean anything.

Firstly, the program must terminate. The operations inside the loop have a fixed cost. Also note that the length of A must eventually reach 0. The floor N/2, is no larger than N/2, and N/t^2 will eventually be less than 1, at which point the next floor will be 0, and the loop will stop.

Now it is obvious that if X isn't in A, the program cannot return a false positive, because it checks for equivalence directly. Before returning true. To show that it will find all members isn't as easy, But it's not that bad simply assert how starting with the assumption that X is infact in A (which is given), each subarray must contain X. Couple that fact with the previous one about termination, and you get that eventually the element will be found.


Time complexity:
So we've talked about termination but not termination speed. Well when you divide a number n by 2 and take the floor, the size of the array will be no larger that size N/2. Formally, you'd use the masters theorem, and assert that T(n) = T(n/2) + O(1), which will let you get the O(log(n)) answer directly. Else, you could just make the argument that multiplying by 1/2 at every step makes the size of the array <= A.length * (1/2)^t, and then just do some algebra to show how this will make The total time logarithmic with respect to A. length.


I hope this helps, correct me if I'm wrong. It's what I learned at uni last year and so I wrote this off of memory.

>>10
Your post was helpful.

But you should refrain from using vanity tripcodes here, it's something only imageboard retards and redditors would do.

>>10
You're not suppose to help him

>>11
Vanity tripcodes != unsecure tripcodes, and this in fact, is not the former. Unless of course you consider 'pQsULI4sXc' to hold some kind of special meaning. I guess only 'imageboard retards' know of such nuances. Let me guess, another one of those kids who doesn't like /g/ or the rest of 4chan, because /prog/ is OH SO MUCH BETTER.

>>13
Yes, I'm one of those kids, /g/ is fucking shit. /prog/ is so much better, indeed.

I'm not bothered by your presence, in fact your post was good. But please remove your name, it doesn't contribute anything to the conversation and even if it's a ``meaningless'' tripcode, you know what consequences this might bring in the future (namely, becoming an insufferable fagstorm). Moreover, a tripcode is not strictly necessary here, you don't need to prove your identity to be helpful.

There's no need to act up like that, I was just making a recommendation.

>>13
pQsULI4sXc doesn't have any particular meaning, but Senjougahara Hitagi does, ``faggot". Now back to /r/programming with you.

I miss kodak-kun

>>14
If you weren't such an insufferable cunt about tripcodes, this would be a better place. If it really bothers you, open your own board and ban them from there like britfa.gs does. Until then, stfu.

>>13
It's an analogue to ``vanity domain''. Vanity domains aren't domain hacks (e.g. ``johnsmi.th''), they're domains people register for the sake of having a domain; to boost their ego.
https://webcache.googleusercontent.com/search?q=cache:http%3A%2F%2Fwww.4chan.org%2Fblog%2F2005%2F11%2F09%2Fin-response-to-anonymity%2F
Read this.

>>15
"
If you keep that up, people aren't going to take you very seriously.

I agree 100% with everything in this article. As a non-Japanese 2channeler living in Japan, I have a special appreciation for anonymous posting; when I post on 2ch, my words are not those of a “gaijin,” but just those of another nanashi-san. It’s the only time I can be completely at ease about my identity as a foreigner. As a matter of fact, when I DO claim that I am not Japanese, people often accuse me of “tsuri” (trolling), i.e. they think that I am a Japanese pretending to be a gaijin.

>>20
You must be a Japanese troll. If you speak good Japanese, what are you doing on world4ch?

>>10

IDIOT.

DO NOT READ CLRS. IT IS A CRAP BOOK WRITTEN BY MORONS.

>>11,14
You're a fucking tool, get back to /g/, please.

Thanks >>10 but that really was over the top.
Orders of complexity can be proven simply by induction.

>>14
Well I disagree with your opinion about tripcodes. Insufferable fagstorms as you call them are caused by shitposting trippers. I tried to write that post with genuine quality, and you can see that. Also, this is my site wide tripcode. I use it for a variety of reasons that happen to not include shittposting and posting for attention. Don't you worry, I won't be here very long, I'm just visiting.

>>15
Even worse, name != tripcode. At least before you were in the right super class, you're devolving. And no /prog/ sucks and you should feel bad. /g/ isn't full of a bunch of morons talking about  Jews and random other crap.

>>22
So MIT and Caltech uses it because?

>>24
Yeah I could have simplified it, but I wanted to include everything that would make it a formal proof, and why those things would be necessary for the full argument. In my experience, at least in the beginning of courses, you have to include each of these items. And in fact I skipped out on formal loop invariants. Proofs for academia tend to be fairly long and verbose, as you probably know.

>>25
back to /g/, ``please''

>>25
/g/ is a lot like /prog/ for noise, but threads here stay forever so when something good happens it's not fleeting at least—it will be here forever. You haven't been here long enough to see the neat things¹ eventualities, so your comparisons are useless. It's still okay not to like /prog/ based on your experience and it doesn't make you a bad person or even bad judge of character for most purposes.

Some things you should know:
- The guy shitting on you about your trip has been here less than six months and speaks for no one but himself.
- People will make fun of you for using a tripcode if for no other reason than because they have something to focus on and a name to slander. If you care about such things it's your problem. OTOH, why the fuck would you use a tripcode if you're that self-conscious?
- >>22 has nothing of substance to say. There's no point in engaging.
- >>24 probably doesn't know much about academia (but that isn't to say he doesn't know much.)
- It is customary to sage if your post is not topical, or if the thread is not topical.
- It is customary to shitpost.
- I can see ur underpants.

1: eg. http://dis.4chan.org/read/prog/1295544154

>>25,27
My post was unnecessary and honestly, I was just partially trolling. I was actually quite taken aback by a post of any quality on /prog/, so I had to do something to restore the balance. My apologies.

>>27
oh wow, go back to reddit

>1-fag poses question
>someone helps him
>attention turned to his tripcode
>tripuser responds to the troll bait
>argument engaged
>le anonymous troll wins again

>>27
Alright I see, it has some valuable content.

I'm not self conscious, like I said, I've been tripping site wide, and have been for a while now. If it wasn't painfully obvious by the name, I'm from /a/ and /v/ and /sci/ and I'm branching out. I don't think I'll ever get used to the shitposting, that usually gets deleted on the image boards or shit on by angry posters.

Well thanks for the link anyways.

>>23
Why should I go back to /g/? I'm not the one who claimed to come from the imageboards.

>>31
Oh uh... you took that more seriously than anticipated. I will level with you, I have never made a completely serious post on /prog/ that wasn't entirely code and/or totally absorbed in discussion of a programming concept.

The sleepsort thread had some hilarious moments. For something with real content, try http://dis.4chan.org/read/prog/1260419313

That thread is full of shit, but has some conversation on FM and even details for implementing an FM synth.

>>32
Because your childish attitude indicates that you belong there.

>>33
Well it's hard to tell when you say things that probably are true, although somewhat baseless.

I find sleep sort to be decently thought provoking. It's a good example of what is and isn't allowed when you do high level programming. I.e. it's the equivalent of saying ALRIGHT NOW SORT THIS LIST IN O(n) time GO.

>>35
The plausible-but-somewhat-amusingly-false posts can be difficult to spot at times. Just take everything said here with a pinch of cocaine.

>>36
The scary thing is you're right, besides the troll bits. Even scarier is the fact that what I think are the troll bit might in fact be the honest parts and vice versa. Well this is an interesting little semishithole you've got going here, I'll be lurking a while to understand the CULTURE. It's surprisingly different than /g/ or /a/. I'm curious as to why you don't give shitposters shit, but that's probably because everything here is a little more laid back and less aggressive.

>>35
Well it's hard to tell when you say things that probably are true, although somewhat baseless.
That's the currency of the second-order conversation around here. It's very subtle.

>>36
Shitposters get lots of shit, which is just more shitposting by definition when WE HAVE NO MODS!! Except when we do. What good is it going to do when some shithead _just_ wants attention?

Lets say i have a function:

(defun foo (n)
  (loop for i = 1 to (1- n) do
    (foo i)))

By simply trying out different n value it becomes clear this executes in O(2^ⁿ) time; however i have no clue how to prove it.

I could say:
T(1) = 1
T(N) = T(N-1)+T(N-2)+T(N-3)+...+T(1)
but i fail to comprehend masters theorem to apply it here.

Alternately i could draw a picture:

              |------------(foo 5)-|------------|----|
           (foo 4)--|           (foo 3)      (foo 2) (foo 1) 
           /     \ (foo 1)      /     \         |
        (foo 3) (foo 2)     (foo 2)   (foo 1)(foo 1)
        /     \       \         \
   (foo 2)   (foo 1)  (foo 1)   (foo 1)
      |
   (foo 1)


but that doesn't seem to really help me generalize this for n input

teh fuck you're talking

stranger senjougahara-kun, see this http://dis.4chan.org/read/prog/1320850110

it's /prog/ at its best :3

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

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

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

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

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

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

>>46
learn how to quote onegai

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"?

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

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

>>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 2^5-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?

>>41
IHBT, except that isn't the original thread.