[orionblastar]

From my limited understanding a list is a data structure that contains an ordered number of items. For example a linked list that has a pointer to the next item in the data structure that keeps the list in order. A tree data structure has sub-sets of linked nodes starting at a 'root' node, much like a tree.

How does time complexity fit into that?

[tptacek]

The list and the tree don't themselves have time complexity; operations on them do. Finding an element in a list takes O(n) time; in the worst case, you have to check every element of the list. Finding an element in a balanced binary tree takes O(log n) time: at each step, you halve the number nodes you need to check.

The balanced binary tree search operation is an example of something whose cost grows very slowly even as the size of the tree grows rapidly.

There are algorithms that are hard the same way the O(log n) tree is easy: they grow exponentially with the size of input, so very small changes in the input size can drastically increase their cost.

[orionblastar]

What is this "O"? This is what I am talking about, the Wikipedia article and even this thread throw out variables without defining what they are. "O" and "n" what are they, how do I calculate them? How do they work? That is why none of this makes any sense that I can understand.

[brudgers]

Seriously, what is "n" often used to signify in math? Stop thinking of reasons to complain and read for comprehension. Then you will be halfway through O(n).

Then if you write down what you think O signifies, you will be at least 3/4 to the answer instead of part way. Nobody can learn for you. Only you can put forth the effort required.

Cowboy up.

[orionblastar]

Most variables in math are unknown until you are given enough information to solve them.

Suppose I gave you J(log y) and then told you that you have to solve for it. What does it mean, how do you calculate it, how does it work, cowboy up and do it man!

What do you mean what are the values of J and y? It is math, just do it! Write down what you think J and y signifies. You will be 3/4th the way to the answer instead of part way. Nobody can learn it but you. Only you can put forth the effort.

[ronyeh]

Hi!

Search for "Big O notation" on Google.

In this case, the O refers to roughly how complex an algorithm is, or how much time it takes to compute the answer.

n is the size of the input to the problem.

For example, if we are searching for a word through a large Charles Dickens book, we are working on an O(n) problem, where n is the number of pages in the book. We say that this problem has an "order of n" time complexity.

This means that if we double the number of pages in the book to 2 * n, the problem will simply take twice as long. All O(n) problems have this property. If you multiply n by a constant size (e.g., 2), the time it takes to complete the problem will be multiplied by that same constant size.

Some problems are harder. For example, we have two long books, and want to see if there is a sentence in Book 1 that also appears in Book 2. Since you have a tech background, you'll realize that an easy solution to this is to write a for loop nested within a for loop.

This type of problem is O(n^2), because the time it takes to solve the problem scales with the square of the problem size. If I double the number of pages of each book (n), the problem actually takes four times as long!

So this problem is O (order) of n^2 (number of pages).

If you read up on Big O notation, you'll learn that some problems can be solved really fast. We call this O(1) or constant time (since 1 is a constant). For example, if I ask you to tell me if a number is even or odd, you can tell me in constant time, no matter how big an integer I give you (i.e., you just look at the last digit and ignore the rest of the ginormous number).

Some problems are harder.... O(n^3) or even O(n * (n-1) * (n-2) * ... * 3 * 2 * 1).

Good luck!

[brudgers]

Suppose I gave you J(log y)

I would say, "Thank you".

[tptacek]

Well, I tried. Good luck!