Sample Dissucssion questions

1. Consider two implementations of a string, which is a (fixed size) array, the other of which is implemented as a linked list. Consider the advantages and disadvantages of each. (See below for some code snipits)
2. For both implementations, write a strlen() member function which returns the length of the string. Using the big-Oh notation, what is the complexity of these two algorithms? If you wanted to make the complexity constant time, how would you do so?

class string_a{
	char s[100];
	
	// Member functions
};
-----
struct node{
	char c;
	next * node;
	};

class string_l{
	node * h;

	// Member functions
};

• Consider the following program:

  for(i=0;i <N;i++)
     for(j=0;j<i;j++)
     	doit();
  

  Exactly how many times will the function doit() be called? If f(N) is the function that expresses how many times doit() is called for a given N, what is the big-Theta is f(N)?