Big O Notation - HELP!

[ANewbieCplusplus]

So im still learning programming and I have came across BIG O NOTATION. I don't really understand it after endless of tutorials and videos to help guide me through it.

How does the process work?
What elements are there?
How can you workout or describe the run-time bounds of an algorithm for example; a linear search algorithm?

Any help would seriously be appreciated!

Thankyou!

[Darkmaster]

can you give an example. I have no idea what you are talking about :/

[ANewbieCplusplus]

I don't want to just give you my algorithm... I want just an e.g. or process on how big 0 notation works, and how I go about working out and describing the run-time of the algorithm?

my algorithm is a linear search algorithm

[dhayden]

Big O notation is a way to describe the performance of an algorithm as size of the input increases. Imagine that you timed your algorithm with input sizes of 10, 50, 100, 500, 1000, 5000, 10,000, etc. What would the graph look like? There is some complicated expression that will give you the run time, but when the input is large, most of the terms become relatively small and one term contributes the most.

So take that linear search. There is some one-time setup in the algorithm. ANd when you find the answer, there is some one-time code for returning the result. All of that takes some constant amount of time REGARDLESS of the input. Let's call that time K1.

Then there's probably a loop the searches for the item. The loop probably does the same thing each time. So it probably takes constant time to go through the loop once. Call that time K2.

But to find the answer, you have to execute the loop many times. Let's say that on average, the item you're looking for is half way through the collection, so if the input is size N then on average, you execute the loop N/2 times.

Now we can estimate the time to run the algorithm. Total time is
K1 (the setup and return time)
+ N/2 * K2 (N/2 times the loop that takes K2 time)

So the total is K1 + N/2*K2. Let K3 = K2/2 so now it's K1+N*K3;

Okay, suppose N is big. Really REALLY big. That graph of K1+N*K3 is going to start looking a lot like N*K3. In other words, K1 is going to contribute only a little to the result.

And that means that the algorithm is O(N).

Specifically, if f(n) is some function of n, then an algorithm is O(f(n)) if, for large values of n, K1*f(n) < algo runtime < K2*f(n) where K1 and K2 are constant and K2>K1.

If you've done precalculus, you'll recognize this as a limit problem.

Hope this helps and doesn't just confuse you even more :(

[Duthomhas]

http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/#Big-O

(There's some links there you can follow too if you want to know more.)

[coder777]

In simple words: The number of steps required to process an algorithm.

Usually loops are taken into account. So O(n) could be:

for(int i = 0; i < n; ++i)
{
  DoSomething();
}

if DoSomething(); would contain such a loop again it would raise the complexity to O(n²)

[ANewbieCplusplus]

I thank you guys a lot

dhayden

coder777

but im still not getting it :(

If I posted my algorithm could someone start me off or write the steps down I need to do to find out the run time of my linear search algorithm?

[armorm2]

string list[5] = 
 { "One", "Two", "Three", "Four", "Five" };

bool search(string searchTerm) {
  for (int i=0; i<5; ++i)
    if (list[i] == searchTerm)
      return true;
  return false;
}

Ok I've provided an list of strings, and a function search(...) which searches the list for the specified searchTerm. As you can see search(...) is performing a linear search through the list of 5 strings. If you are given the code above, and asked to find out the run time of search(...) function, this means you have to analyze the execution of search(...), taking into account the size of the list being search can grow, and thus the time it takes to search the list varies based on how many items are in the list. You'll see that whenever search(...) function executes, it first begins executing the for loop. So now it's time to analyze how long does it take the for loop to execute? Based on the loop condition, i starts at 0, and takes on possible values 0, 1, 2, 3, 4 --> 5 possible values, in the worst case (which is what is being asked when you are asked to provide the big-O, or upper bound, time complexity of an algorithm). Therefore, the loop takes time O(5) or O(n), where n = 5 in this example, but it can be variable in general so that's why you see in many places that it is written O(n). N is just the size of the input, or in this case n = size of list being searched.... Now continuing the analysis of search(...) function, we've determined the for loop executes in O(n), so the next statement to execute in search(...) function is the "return false", assuming no match for our searchTerm found in the list. "return false" executes in O(1) or constant time, since it takes constant time for the C++ runtime environment to execute a return which is equivalent to popping from the stack the current function being executed... anyways, to sum it up now that all statements in the search(...) have been analyzed individually:

O(n) for loop + O(1) return statement
=> T(n) = O(n) for the search(...) function

hopefully this helps!

[JoshuaMostafa]

Big O is used to calculate algorithm cost. It calculates the cost based on input size. If the time to finish a task in a certain algorithm is independent from the size of the input, then it will take O(1) which is constant time. Tasks like this include addition, ...etc.

If the time to finish a task in a certain algorithm depends on the size of the input, then it will take O(n) which is linear time or O(n^2), O(n*log(n))....etc. Tasks like this include sorting numbers stored in a linked list, searching for an element in a vector, ...etc

Big O notation is probably the easiest concept in Computer Science, but it is extremely important.