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]

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-lite/how-to-post.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-lite/how-to-post.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