computational time

[mickey]

Hello,
could you suggest me any link where find information about algorithms that work in logarithmic and quadratic time. (And how to compute it) I'd like build the same alg and see the time different between them. Will it be possible have the same computation with this different two features?

thanks.

-- EDIT
I think to order a list of numbers or other....

[jacek]

Does logarithmic time mean O(log n) or maybe O(n log n) will be enough? Because in the latter case you can find good examples quite easily.

[mickey]

Does logarithmic time mean O(log n) or maybe O(n log n) will be enough? Because in the latter case you can find good examples quite easily.
Ok, I mean Olog(n) (but If you have some link with O(nlog(n)) I'll read it too)....

[wysota]

Lookup in a tree is log(n) with the base of the number of children each node has - thus log2(n) in a binary tree. Bubble sort is O(n^2), because it iterates n times over a table of up to n elements. Most sorting algorithms are O(nlogn).

[jacek]

Ok, I mean Olog(n)
If the efficient algorithm is O(log n), then usually it's hard to find an inefficient version than would be worse than O(n). Of course you can always try to spoil the implementation to make it O(n^2), but I don't think this is what you want.

[mickey]

Sorry but I don't necessary sort the list: I must only find one element in the list in logn time!!!
EDIT -- But in a sorting, Do I have logn time only with a tree??

[jacek]

Sorry but I don't necessary sort the list: I must only find one element in the list in logn time!!!
You can't find an element in a list in O(log n), but it's possible with trees or arrays.


But in a sorting, Do I have logn time only with a tree??
It takes O(nlog n) to sort elements using a tree. Only insertion, removal and look up operations are O(log n) in a tree.

[wysota]

You can achieve O(logn) complexity in finding an element in a list. But the list has to be presorted first (which in itself of course is O(nlogn)) - then you can use binary search to find the item you need. So if you can presort the list (once), you can have O(logn) lookup (many times).

[jacek]

You can achieve O(logn) complexity in finding an element in a list. But the list has to be presorted first (which in itself of course is O(nlogn)) - then you can use binary search to find the item you need.
You can't use binary search on a list --- it doesn't allow random access.

[wysota]

Depends what you call a list. QList allows random access, so does an array (and a list can be implemented using an array or a vector). A linked list doesn't support random access - that's obvious. An algorithm doesn't enforce implementation, so I wasn't talking about any specific container, just about the algorithm itself.

[mickey]

You can achieve O(logn) complexity in finding an element in a list. But the list has to be presorted first (which in itself of course is O(nlogn)) - then you can use binary search to find the item you need. So if you can presort the list (once), you can have O(logn) lookup (many times).

Do you mean with presorted "sort the list before search"? In that cas, Yes, I can do everything I like. But I'd like don't use QT, then I call "list" a vector. If I understand right, for the sort I can't do better than O(nlogn). Is it that? Anyway, it seems that using a vector I can't use a tree; maybe I need implement my own tree...

[wysota]

Do you mean with presorted "sort the list before search"?
Correct.

If I understand right, for the sort I can't do better than O(nlogn). Is it that?
Correct again.

Anyway, it seems that using a vector I can't use a tree; maybe I need implement my own tree...
If you want to sort a list, you don't need a tree. If you want to sort a tree, you can have a tree-like structure that is always sorted like a heap or traverse the tree in a sorted order, like with Binary Search Tree. If you want to look up an element in the tree, it will take O(logn), provided that the tree is sorted (like the BST tree again). If you want even faster lookup, use a hashing table - the complexity of lookup is then O(1) with worst case of 'n' if all elements end up in a single node. You can also combine the hash table with a tree which will have the worst case of logn.

[mickey]

1. I read some pages and I'm more confused now; I read that search in abinary-tree is O(n) (i.e. create a tree with this elements in input with this order: 10,20,30,40,50 -> O(5) = O(n).
I read (If I understand right) that we can count on the fact that we can't always unlucky and than the input distribution, on average, can be better: for this reason we can have O(logn) (30,20,40,10,50) in in this order). Is it this?

2. If I can obtain a search in OLogn(n) with an sorted array, for clearly, I prefer this....I guess it'll be the same of a sorted vector<int>

[wysota]

1. I read some pages and I'm more confused now; I read that search in abinary-tree is O(n) (i.e. create a tree with this elements in input with this order: 10,20,30,40,50 -> O(5) = O(n).
This is the worst case scenario for an unbalanced tree - in the above mentioned case your tree becomes a list. On average the complexity is O(logn) and balancing the tree (see AVL Trees) guarantees O(logn) lookup in the worst case too (the insertion is slower though).


2. If I can obtain a search in OLogn(n) with an sorted array, for clearly, I prefer this....I guess it'll be the same of a sorted vector<int>

Yes, a vector is also an array.

[mickey]

what I don't still understand is:


//pseudo code
int a[5] = {10,20,30,40, 45}
bool search (int a[5], int value) {
for (int i=0; i< a.lenght; i++)
if (value == a[i]) return true;
return false;
}
search (45); -> this is what'll happen in the worst case. And it's O(n).......and array was sorted.....It isn't O(logN)

[marcel]

what I don't still understand is:


search (45); -> this is what'll happen in the worst case. And it's O(n).......and array was sorted.....It isn't O(logN)


Yes, great analysis!
It is O(n) because you searched in an array, not in a balanced binary tree and because you used the wrong searching algorithm.
To get the time you want you have to use a O(logn) sort algorithm such as qsort (http://en.wikipedia.org/wiki/Quicksort) to sort the array and then use binary search (http://en.wikipedia.org/wiki/Binary_search) to find a value.

[wysota]

The very basic implementation of binary search in an array is more or less like this:

int a[5] = {10,20,30,40,45};
int search(int *tab, int value, int low, int high){
int med = low+(high-low)/2;
if(tab[med]>value)
return search(tab, value, low, med);
else if(tab[med]<value)
return search(tab, value, med, high);
else if(tab[med]==value)
return med;
return -1;
}
When you call it as search(tab, 45, 0, 4) it will compare to 30, then to 40 and then to 45. It requires three steps for a 5 item array, which is more or less O(logn).