Time analysis

[mathon]

hello,

i have a question regarding time analysis, respectively calculating the
Big O. For example when i have this function:

void sequence::attach(const value_type& entry)
{
if(!(is_item()))
{
cursor = tail_ptr;
}
 
if(cursor == NULL)
{
list_head_insert(head_ptr, entry);
cursor = head_ptr;
tail_ptr = head_ptr;
}
else
{
list_insert(cursor, entry);
precursor = cursor;
cursor = cursor->link();
}
 
++many_nodes;
 
node* cursor1;
node* precursor1;
for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
{
precursor1 = cursor1;
}
tail_ptr = precursor1;
}
 

Does there exist an easy concept how i can calculate the Big O for the
previous function for example...?

matti

[mlimber]

ma****@gmx.at wrote:

hello,

i have a question regarding time analysis, respectively calculating the
Big O. For example when i have this function:

void sequence::attach(const value_type& entry)
{
    if(!(is_item()))
    {
        cursor = tail_ptr;
    }

    if(cursor == NULL)
    {
        list_head_insert(head_ptr, entry);
        cursor = head_ptr;
        tail_ptr = head_ptr;
    }
    else
    {
        list_insert(cursor, entry);
        precursor = cursor;
        cursor = cursor->link();
    }

    ++many_nodes;

    node* cursor1;
    node* precursor1;
    for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
    {
        precursor1 = cursor1;
    }
    tail_ptr = precursor1;
}
 

Does there exist an easy concept how i can calculate the Big O for the
previous function for example...?

First, this is not a C++ *language* question and so is off-topic here
(see http://www.parashift.com/c++-faq-lit....html#faq-5.9).
You should ask in comp.programming or similar.

Second, we're not here to do your homework for you
(http://www.parashift.com/c++-faq-lit....html#faq-5.2).

I can tell you that the standard C++ linked list is O(1) to insert and
O(N) to traverse (cf. http://www.sgi.com/tech/stl/List.html).

Cheers! --M