Some questions about algorithm analyzis

Question

Uh, hi! Well, I'm talking about the thing of "O(n)" and "o(n)" related to algorithms. I don't know the technical name, then I called as "algorithm analyzis" (sorry). Anyway, the questions:

1. Well, hm ... How I can "analyze" an algorithm to determine if them is "O(n/2)", for example? What consider?
2. On a sort algorithm for example, "n" is the number of elements to sort, and the operation inside parenthesis is the time to sort them. But I did see on a thread, that on a get algorithm is O(n/4), but I can't figure "n" being the number of objects to get, or really is this? Or varies, depending the algorithm's type?
3. Some considerable info, about this, that I need know?

I apologize so much for my english, and if I did used very "superficial" terms.

Answer 1

You are basically asking for an answer on how you can analyze running time of algorithms. There is no shortcut to this, you must study the theory. You can google it. Here are some links from where you can start:

How to find time complexity of an algorithm

introduction to algorithm complexty

Answer 2

That O is the complexity of an algorithm. There can be several types of complexities. You can measure the time complexity, that is, how complex the algorithm is in time. Or in memory. Or in disk storage space. The latter two are very similar.

Time complexity: Determines the needed number of operations based on the size of input.

Memory or Disk storage complexity: Determines how much space will be allocated based on the size of input.

O(n/2) time complexity means that you will need to process half as many operations than the size of the actual input.

Since the input is a positive integer, to be able to do analytical stuff you need to assume that n -> infinity, that is, you have a LOT of input items.

Then O(n/2) is a linear complexity, since (n/2)' = 0.5. 0.5 is a scalar value and scalars do not really change the complexity in the infinity. There is a de facto difference when your input has a finite size, but that's another question to tackle with. So

O(n/2) <=> O(n)

Since both are linear, even if the line of Y = n/2 is different from the line of Y = n.

O(n^2) is more complex, since (n^2)' = 2 * n.

So, to understand complexities, you need to understand the derivatives (or differentials in case of more dimensions) of the function which describes the complexity. You find the function correctly if it describes the number of operations for all possible inputs.

Example of determining the complexity:

Let's consider the case when we have a finite, ordered set of numbers where we are searching for a specific number. We guess at the middle of the set for the first time. If we guessed it right, the algorithm stops. If not, then we check for the number in a similar way in the first half if the number is actually smaller than the one we found at the given index and in the second half otherwise. This algorithm is called binary search. So, how do we determine its complexity? First, we need to observe that there is a chance that we guess the position right from the very first time, so the best-case-scenario is of O(1). However, if we are not so lucky, we might need to halve the set many times. So the complexity question is reduced to the question of: how many times might we need to halve the set? It is the number, which, as the power of 2 would yield the size of the input. This is the definition of the logarithm, so binary search is logarithmic.

When you calculate storage complexity, you do a similar calculation.