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:
-
int a;
a=b;
-
for (int i=0; i<n; i++)
array[i]=0;
-
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
a++;
For Answers, click
here
Back to Libraries and Running Time Measurements Lab click
here
Copyright: Department of Computer Science, University of Regina.