Assuming your data has been put into a linked list with the following structure, it would go something like this:
data.start = 0
data.end = 100
data.value = 100
data.next = [next data entry]
code:
Code:
if (data is not sorted)
{ sort(data by start) }
nextdata = data;
while (date.next is NOT NULL) // search the entire linked list
{
nextdata = datanext.next;
if (data.end <= nextdata.start)
{
data = data.next
nextdata = data
}
else if (data.start = nextdata.start)
{
if (data.end >= nextdata.end)
{
break data up and insert into sorted linked list
}
else
{
break data up and insert into sorted linked list
}
}
else if (data.start < nextdata.start)
{
if (data.end >= nextdata.end)
{
break data up and insert into sorted linked list
}
else
{
break data up and insert into sorted linked list
}
}
}
O(break data up and insert into sorted linked list) = O(log(n))
O(while loop) = O(n(n-1)+(n-1)(n-2) ...) ~ O(n(n+1)n) = O(n^3)
So you have a running time close to O(n^3 * log(n)) for the big loop, and the sort function can be done in like n log n time thus being slower than n^3 * log(n).
Login
Register
FAQ
Search
