I am just studying for my class in Algorithms and have been looking over QuickSort. I understand the algorithm and how it works, but not how to get the number of comparisons it does, or what logn actually means, at the end of the day.

I understand the basics, to the extent of :

x=logb(Y) then
b^x = Y

But what does this mean in terms of algorithm performance? It's the number of comparisons you need to do, I understand that...the whole idea just seems so unintelligible though. Like, for QuickSort, each level K invocation involves 2^k invocations e开发者_运维技巧ach involving sublists of length n/2^K.

So, summing to find the number of comparisons :

log n
Σ 2^k. 2(n/2^k) = 2n(1+logn)
k=0

Why are we summing up to log n ? Where did 2n(1+logn) come from? Sorry for the vagueness of my descriptions, I am just so confused.

If you consider a full, balanced binary tree, then layer by layer you have 1 + 2 + 4 + 8 + ... vertices. If the total number of vertices in the tree is 2^n - 1 then you have 1 + 2 + 4 + 8 + ... + 2^(n-1) vertices, counting layer by layer. Now, let N = 2^n (the size of the tree), then the height of the tree is n, and n = log2(N) (the height of the tree). That's what the log(n) means in these Big O expressions.

below is a sample tree:

      1
    /   \ 
   2     3
  / \   / \
 4   5 6   7

number of nodes in tree is 7 but high of tree is log 7 = 3, log comes when you have divide and conquer methods, in quick sort you divide list into 2 sublist, and continue this until rich small lists, divisions takes logn time (in average case), because the high of division is log n, partitioning in each level takes O(n), because in each level in average you partition N numbers, (may be there are too many list for partitioning, but average number of numbers is N in each level, in fact some of count of lists is N). So for simple observation if you have balanced partition tree you have log n time for partitioning, which means high of tree.

1 forget about b-trees for sec

here' math : log2 N = k is same 2^k=N .. its the definion of log , it could be natural log(e) N = k aka e^k = n,, or decimal log10 N = k is 10^k = n

2 see perfect , balanced tree

1
1+ 1 1 + 1 + 1+ 1 8 ones 16 ones etc

how many elements? 1+2+4+8..etc , so for 2 level b-tree there are 2^2-1 elements, for 3 level tree 2^3-1 and etc.. SO HERE'S MAGIC FORMULA: N_TREE_ELEMENTS= number OF levels^ 2 -1 ,or using definition of log : log2 number OF levels= number_of_tree_elements (Can forget about -1 )

3 lets say there's a task to find element in N elements b-tree, w/ K levels (aka height)

where how b-tree is constructed log2 height = number_of_tree elements

MOST IMPORTANT

so by how b-tree is constructed you need no more then 'height' OPERATIONS to find element in all N elements , or less.. so WHAT IS HEIGHT equals : log2 number_of_tree_elements..

so you need log2 N_number_of_tree_elements.. or log(N) for shorter

To understand what O(log(n)) means you might wanna read up on Big O notaion. In shot it means, that if your data set gets 1024 times bigger you runtime will only be 10 times longer (or less)(for base 2).

MergeSort runs in O(n*log(n)), which means it will take 10 240 times longer. Bubble sort runs in O(n^2), which means it will take 1024^2 = 1 048 576 times longer. So there are really some time to safe :)

To understand your sum, you must look at the mergesort algorithm as a tree:

         sort(3,1,2,4)
        /            \
   sort(3,1)      sort(2,4)
    /     \        /     \
sort(3) sort(1) sort(2) sort(4)

The sum iterates over each level of the tree. k=0 it the top, k= log(n) is the buttom. The tree will always be of height log2(n) (as it a balanced binary tree).

To do a little math:

Σ 2^k * 2(n/2^k) = 
2 * Σ 2^k * (n/2^k) =
2 * Σ n*2^k/2^k = 
2 * Σ n = 
2 * n * (1+log(n)) //As there are log(n)+1 steps from 0 to log(n) inclusive

This is of course a lot of work to do, especially if you have more complex algoritms. In those situations you get really happy for the Master Theorem, but for the moment it might just get you more confused. It's very theoretical so don't worry if you don't understand it right away.

For me, to understand issues like this, this is a good way to think about it.