[NecroWinter]

Hey everyone, I just have some quick questions that i'd like answered. Nothing too demanding if you already know this stuff IMO. A lot of the tutorials online try to bog me down with the math behind algorithm analysis, and quite frankly, the class im in doesnt concern its self with that, and ill be busy with that when I take a class on algorithms specifically(as opposed to algorithms & data structures... which im in now)

So anyway, question 1:
I know that if you have nested for loops, theres a good chance you have O(n^2), and if you have a sorting algorithm that halves the dataset over and over you have O(log n) time. How do you determine the other common run times easily, such as n log n?

Question 2:
http://en.wikipedia....ity#Linear_time
According to this wikipedia entry, O(n) time is usually desirable. I ask, why is that? Wouldnt log n time be best? Is there something im missing? are each common run times associated with certain kinds of algorithms?

[blackcompe]

1) Like you said it's log n when the size of the problem is halved.

For something simple, it's easy:

for(int i = 0; i < n; i++) //Θ(n)
     for(int j = 0; j < n; j*=2) //Θ(log(n))
          ;

T(n) = Θ(nlog(n))

For a recurrence, you can use the master theorem, substitution, or the recursion-tree method. See Introduction to Algorithms by Cormen et al.

BinarySearch(A[0..N-1], value, low, high) {
.
.
.
if (A[mid] > value)
    return BinarySearch(A, value, low, mid-1)
else if (A[mid] < value)
    return BinarySearch(A, value, mid+1, high)
}

T(n) = T(n/2);

Use the recursion-tree method for this.

function merge_sort(m) {
.
.
.
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
}

T(n) = 2T(n/2) + O(n)

Use the master theorem for this.

2) Sub-quadratic algorithms are considered fast for problems with large input sizes (>= 10⁶), so linear algorithms are of practical use. Logarithmic algorithms are even better, but they are harder to code.

This post has been edited by blackcompe: 21 October 2011 - 11:12 PM

[Nikitin]

blackcompe, on 21 October 2011 - 08:16 PM, said:

Logarithmic algorithms are even better, but they are harder to code. don't exist for most of the problems.

FTFY

[Veitch]

Quote

I know that if you have nested for loops, theres a good chance you have O(n^2), and if you have a sorting algorithm that halves the dataset over and over you have O(log n) time. How do you determine the other common run times easily, such as n log n?

Example: You call an O(log n) algorithm within a loop that is executed n times.

Quote

Question 2:
http://en.wikipedia....ity#Linear_time
According to this wikipedia entry, O(n) time is usually desirable. I ask, why is that? Wouldnt log n time be best? Is there something im missing? are each common run times associated with certain kinds of algorithms?

Despite not having an O(log n) algorithm for every problem, a O(log n) algorithm is not better than a O(n) algorithm in every case. I.e. you want to sort an array and you know that the number of elements won't be very high, but you need to sort very often. Then you are better off using an algorithm that doesn't need a lot of constant time, but is maybe in a worse time complexity class than others. That algorithm may perform much better for a small number of elements.

[CreamDelight]

In your question number 1, you just have to visualize the flow of the code..
example..

        for(...)
        {
           for(...)
           {
               for(...)
               {}
           }
        }

visualizing this code, you'll see that you will undergo a depth of 3 loops.. So you can say that it is Big O(n^3) or n cube..

other example is binary search tree algorithm.. which divides every subset he encounters by two, so decreasing the range of values he will use.. visualizing the algo you find that it is Big O(log n) because the algo chops the subset by two..

QUESTION #2..
if your asking the fastest worst case.. then it Big O(1)..

[Veitch]

Quote

visualizing this code, you'll see that you will undergo a depth of 3 loops.. So you can say that it is Big O(n^3) or n cube..

You can't say that without knowing how often the the loops are executed and what happens within.