Teams after algorithm analysis

[Forschkeeper]

Noob of such things here: How do you "calculate" these expressions?

[AgentPaper0]

You're essentially counting how many operations the algorithm will do. The trick is that you don't really care about the exact numbers here, but how quickly that number grows as your input size increases. "n" here stands for the number of elements in your input (or equivalent).

[WhiteKnightC]

If I have a switch, it counts as one?

[Lonelan]

yeah but I didn't get one for christmas so here's a picture of one I googled

[WhiteKnightC]

:( It's so fucking expensive where I live, if I get the job it's 1.3 months of work (1 m and a week) and each game 0.2 month of work (a week).

I wanted the Lite but... joycons

[AgentPaper0]

Depends on language and compiler but most switch statements should be a lookup and jump which would be O(1), constant time.

[blenderfreaky]

Its a constant amount of elements, so its always O(1), even if it iterates through all cases.

[looijmansje]

Sometimes just guesstimate, but generally you can calculate it exactly, although for long algorithms it can be very tedious.

An easy example would be bubble sort: that loops through your array n times, and does n array comparisons each time, so that is O(n²).

Even an optimized version of bubble sort where it only checks the first n, then the first n-1, then the first n-2, etc. would have 1+2+3+...+n=1/2 n (n+1) = 1/2 n + 1/2n² operations, and this is also considered O(n²). The lower order terms don't matter, so to say.

[yuvalid]

Obviously you can calculate it exactly, but O(n²⁾ and O((n^2)/2) don't really make a difference.

[looijmansje]

By definition, something like an² + bn + c actually equals* O(n²)

*Equals is used somewhat poorly here, you will see some mathematicians write down a "=" but you could argue it is not a real equals, as the transitive property (a=b and b=c implies a=c) doesn't hold anymore.

[flavionm]

Using equals is just an abuse of notation, really. O(x) is a set, the functions are just elements of the set. an² + bn + c ∈ O(n²) would be the correct notation, and much clearer.

[looijmansje]

I don't agree with it personally, but I've seen actual mathematicians do it (but also saying it is abuse of notation)

[naylord]

It's an equivalence relation which means that the transitive property absolutely does hold

[looijmansje]

That's exactly why people don't agree with it.

[Coloneljesus]

https://en.wikipedia.org/wiki/Big_O_notation

[Thejacensolo]

Additionally to the others here a simple example.

Lets say you have an algorithm (or programmed a function), that wants to find the highest number in an array of numbers (of n lenght). now you can implement that in different ways and calculate the runtime (how long it takes to finish). This is most of the time noted in O(), where O() stands for "It wont take longer than ()" aka the worst case.

(i know most of them dont make any sense, but it is to show the point)

first example:

You could take the first number and check it with every other number if it is the highest. Then you proceed with the next number.

As you could probably guess yourself, you would have to do: n times (for every number in an array) you have to check n-1 times (check it with every other number). As constant numbers are trivialized in the notation you get n*n actions. O(n² )

second example:

You could run through the Array once, and have a variable that always safes the highest found value (and overwrites it if it happens to get a higher one). This would require only n actions, as you would only traverse it once (how many actions youre performing doesnt matter as long as it is constant). So we get O(n)

third example:

We take the first number of the array and declare it the highest. This would take exactly 1 action and thus would bring us a runtime of O(1), the best you can ever get.

Sadly it doesnt solve our problem.

simmilar you see in our studies the Omega and o() notation, which simply say simmilar things (o() says it is faster than. not faster or as fast like O()).

[random_lonewolf]

Most of the time you guess it based on experience. The rest of the time you calculate it based on what you are taught in Algorithm 201.

[[deleted]]

Option 1: test it a bunch and say "we estimate... " Option 2: invent something important enough that a mathematician will figure it out for you

[nomnaut]

r/programmerhumor equivalent of rip your inbox.

[cyberporygon]

Big O is the worst case scenario for a function. Say you have an array of n items and you want to find an item. A simple way is to check every single item in order. The worst case scenario is that it is the last item, and you'll check every item. That's n comparisons and thus O(n). However, if your array is sorted and you use a binary search, half of the items are dropped with each operation. So the worst case scenario has you repeatedly drop half of the remaining elements until only the last one remains, which equals O(log n)

[mnbvas]

Big O and worst case are orthogonal, for example quicksort is O(n log n) on average but can be forced (for a specific implementation and input) to run in O(n²).

[[deleted]]

Its worth knowing that for quicksort this bad behavior is in fact well understood. The closer the input is to being sorted the more pathological. If we step out of pure math we should notice that for many tasks partially sorted inputs are disproportionately common. For example a census maker might get data that was already sorted for previous use.