Computer Science- Time Complexity?

Question

related questions are all over the place, but I haven't seen this one yet (anywhere on the web for that matter): How do you know when a code segment has a time complexity of O(logn)? What's the difference between O(logn) and O(nlogn)? What kinds of code segments have these types of time complexities?

the only thing i could figure out about this damn topic is that O(nlogn) is slightly less efficient than O(n), and O(logn) is a lot more efficient than O(n). Also the sorting method (called quicksort by some) has a time complexity of O(logn). The only problems is I have no damn clue how or why this is...

Answer 1

The best way to think about big-O notation is that the bit between the parentheses is the polynomial for the number of operations you'll need to do to complete the algorithm.

For example, lets say you're outputting every element of an array:

void OutArray(int[] foo)
{
for (int i = 0; i < foo.Length; i++)
{
//output foo[i]
}
}

You'll touch each element of foo during a run of the algorithm. There are n elements (because it's not constant... you can have any number of them, so that number is 'n'). So this is an O(n) algorithm.

Some algorithms are called constant time. The bit that says //output foo[i] up there only has to hit one element, it just outputs. There's a constant number of elements, so this is an O(1) algorithm.

O(log n) and O (n log n) algorithms are more complex, in general. An O(log n) algorithm usually can shortcut around parts of the input... for example traversing to some leaf node in a binary tree. You start at the root, pick a child, then pick a child of that, and so on... you take a path through the tree with the height of the tree, but you don't need to hit all the n elements of the tree. The height is related to the total number of elements in the tree in a logarithmic relation, so going down the path is O(log n).

Sorting, with the exception of some very specific cases where certain assumptions can be made, is O(n log n) at its most efficient. This is because to sort some arbitrary input, you need to hit each element AND you need to order them somehow. The proof for this time complexity is something you'll probably need to know at some point, sorting is very important to CS.

O(n^2) algorithms tend to be cases where you take one element, then do something to all the other elements in the input, then go to the next element, go to all the other elements in the input, and so on. You hit n elements, n times. So to run, your algorithm needs n * n operations, so O(n^2).

The Travelling Salesperson problem was mentioned above... this one is different. Algorithms can be put into some specific classes based on complexity... what I've mentioned here are all in set P, because they all have polynomial time solutions (1, n, log n, n log n, n*n, these are all polynomials). The travelling salesperson problem is in NP, because it doesn't have a polynomial time solution... it's exponential. As the number of cities increases, the number of operations needed to solve it go up exponentially... so it's like O(2^n). You'll get to that stuff eventually, but probably you don't need to worry about it for now.

Regarding quicksort, think about what it's doing, and how many other elements each element is compared to. Try drawing it out on paper if it helps you... start with the overall input set, then do each of the recursive calls on subsets separately.

Answer 2

A program with a Big O(logn) is when you would be finding an item in a binary search tree.

Big O (nlogn) is doing a sort such as a heapsort.

By the way the previous answer was wrong the traveling salesmen would be Big O(n!)

Answer 3

do you have this for a class? your textbook should cover it. mine is in a box somewhere. big O, little O notation, we called it.

n is your input size. big O is maybe the upper limit on how long the program will take. there is a way to work out, based on the size of the problem, how long things will take. a common example is the travelling salesman problem, where a salesman tries to find the quickest route to visit a set of cities with interconnecting roads of various length. your input, n, would then be the number of cities. that grows fast, maybe O(n^2), i forget.

first year computer science stuff.

Answer 4

in many colleges, workstation engineering is a area of expertise interior of electric powered engineering. In some faculties, this may be a separate discipline. there are particular courses you will possibly take up common with all engineering disciplines which comprise electric powered fundamentals, statics, dynamics, thermodynamics, potential of fabric. you will additionally possibly take standard electric powered engineering courses which comprise courses in transistor circuits, hassle-unfastened potential engineering, and digital communications, alongside with a physics sequence, chemistry sequence, calculus, differential equations, linear algebra, etc. you will take those courses on your freshman and sophomore years. on your junior and senior years you will take courses particular to digital electronics and computers that are orientated in the direction of workstation shape, the layout of microprocessors and computers.