# CS210 Lab: Libraries and Running Time Measurement Prelab

## Refresher:

Big O notation is used for characterizing how an algorithm (or piece of code) acts for different problem sizes.
• For instance, if we want to insert a node at the beginning of a linked list, no matter how many nodes are in the linked list, the insertion will always take the same amount of time. Therefore, we can say that the runtime is constant or O(1) (for inserting at the beginning of a linked list).
• However, if we want to insert a node into an ordered linked list, some time will be spent traversing the linked list finding an appropriate location. The worse case will be when the entire list is searched. In this case, the runtime will depend on the number of nodes. To represent this, we say O(n). This is like saying that the runtime depends on the number of nodes (or the problem size)

## Prelab Questions:

The following questions are designed to get you thinking more about big O. For each of the following code fragments, specify the big O expressions:
1. int a;
a=b;

2.
3. for (int i=0; i<n; i++)
array[i]=0;

4.
5. for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
a++;