GNUplot for Algorithm Analysis

Sorting and Searching Experiments in C on Ubuntu

Analysis of Algorithms Lab

1 What is GNUplot?
GNUplot is a command-line driven graphing utility that can be used to visualize mathematical
functions and experimental data. It can be used interactively from the terminal or through
script files, and it can generate output such as PNG, PDF, SVG and other formats.
In this laboratory, GNUplot will be used to visualize the execution times obtained from C
programs implementing searching and sorting algorithms.
The basic workflow is:

C Program → Measure Execution Time → Save Data → GNUplot → Graph → Interpretation

GNUplot is therefore the visualization tool. It does not automatically determine the
theoretical time complexity of an algorithm.

2 Why Use GNUplot in Algorithm Analysis?

Suppose a searching algorithm is tested for different input sizes:

n execution_time
1000 0.00001
2000 0.00002
4000 0.00004
8000 0.00008
16000 0.00016

The first column represents the input size n, and the second column represents the measured
execution time.
GNUplot can convert this table into a graph.
The graph allows us to visually study how execution time changes as n increases.
For example:
• Linear Search has theoretical worst-case complexity O(n).
• Binary Search has theoretical worst-case complexity O(log n).
• Bubble Sort has theoretical average/worst-case complexity O(n2 ).
• Insertion Sort has theoretical average/worst-case complexity O(n2 ).
• Merge Sort has theoretical best/average/worst-case complexity O(n log n).
The experiment allows students to compare the theoretical prediction with measured behav-
ior.

1
 3 Installing GNUplot on Ubuntu
Open the terminal and execute:
1 sudo apt update
2 sudo apt install gnuplot

After installation, check whether GNUplot is available:

1 gnuplot -- version

A version number should be displayed.

For example:

gnuplot 5.x

The exact version depends on the Ubuntu distribution and repository available on the system.

4 Starting GNUplot
Type:
1 gnuplot

The prompt changes to something similar to:

gnuplot>

GNUplot commands can now be entered directly.

For example:
1 plot x

This plots the function:

y = x.
To leave GNUplot:
1 exit

or:
1 quit

5 The Data File

For algorithm experiments, the C program should normally write the measured results to a text
file.
A simple data file might be:

1000 0.0012
2000 0.0024
4000 0.0048
8000 0.0097
16000 0.0194

2
 Suppose the file is called:

[Link]

Each row represents one experiment.

The first column is:

n = input size
The second column is:

T (n) = measured execution time

By default, GNUplot can read whitespace-separated data files. The using specification
selects which columns are used for the coordinates. For example, using 1:2 means that column
1 is used for x and column 2 for y.

6 First GNUplot Plot

Start GNUplot:
1 gnuplot

Then execute:
1 plot " linear . dat " using 1:2

The command means:

• "[Link]" – read data from this file.
• using 1:2 – use column 1 for the X-axis and column 2 for the Y-axis.
• plot – create a two-dimensional plot.
GNUplot’s using mechanism allows particular columns or expressions based on columns to
be selected from a data file.

7 Adding a Title and Axis Labels

A graph should clearly identify what is being measured.
Use:
1 set title " Execution Time vs Input Size "
2 set xlabel " Input Size ( n ) "
3 set ylabel " Execution Time ( seconds ) "

Then plot:
1 plot " linear . dat " using 1:2

A grid can also be added:

1 set grid

Therefore, a simple complete interactive example is:

3
1 set title " Execution Time vs Input Size "
2 set xlabel " Input Size ( n ) "
3 set ylabel " Execution Time ( seconds ) "
4 set grid
5

6 plot " linear . dat " using 1:2

The set grid command adds grid lines corresponding to the axis ticks.

8 Displaying Points and Lines

A plot can be displayed using points:
1 plot " linear . dat " using 1:2 with points

or lines:
1 plot " linear . dat " using 1:2 with lines

or both:
1 plot " linear . dat " using 1:2 with linespoints

For algorithm experiments, linespoints is often convenient because it shows both the mea-
sured data points and the connection between successive points.

9 Adding a Legend
When multiple algorithms are plotted, a legend is important.
For example:
1 plot " search . dat " using 1:2 \
2 with linespoints title " Linear Search " , \
3 " search . dat " using 1:3 \
4 with linespoints title " Binary Search "

The title associated with each plotted dataset supplies its entry in the key (legend).
GNUplot calls this area the “key”. The command
1 set key

enables it, while:

1 unset key

disables it.

10 A Complete Search-Algorithm Example

Suppose a C program produces:

[Link]

with:

4
 # n Linear Binary
1000 0.000012 0.000003
2000 0.000024 0.000003
4000 0.000047 0.000004
8000 0.000095 0.000004
16000 0.000190 0.000005
32000 0.000380 0.000005
The first line beginning with # is a comment and is ignored by GNUplot’s default data-file
comment handling.
The columns are:
Column Meaning
1 Input size n
2 Linear Search time
3 Binary Search time
The graph can be generated using:
1 set title " Linear Search vs Binary Search "
2 set xlabel " Input Size ( n ) "
3 set ylabel " Execution Time ( seconds ) "
4 set grid
5

6 plot " search . dat " using 1:2 \

7 with linespoints title " Linear Search " , \
8 " search . dat " using 1:3 \
9 with linespoints title " Binary Search "

11 Understanding the using Command

Consider:
1 plot " search . dat " using 1:3

This means:

x = column 1
and

y = column 3.
Therefore, if the data are:
1000 0.010 0.002
2000 0.020 0.002
4000 0.040 0.003
then:
1 using 1:2

plots the second column against the first column, whereas:

1 using 1:3

plots the third column against the first column.

This is one of the most important GNUplot concepts for this laboratory.

5
 12 Generating the Data from C
GNUplot does not measure the execution time of your algorithm.
The C program must perform the experiment and write the measurements to a file.
A simple example is:
1 # include < stdio .h >
2 # include < time .h >
3

4 int main ( void )

5 {
6 clock_t start , end ;
7 double time_taken ;
8

9 start = clock () ;
10

11 /* Algorithm being tested */

12 /* Example : search or sorting function */
13

14 end = clock () ;
15

16 time_taken =
17 ( double ) ( end - start ) / CLOCKS_PER_SEC ;
18

19 printf ( " Time = % f seconds \ n " , time_taken ) ;

20

21 return 0;
22 }

The function clock() is declared in <time.h>. Its return value is converted to seconds using
CLOCKSP ERS EC.T heClibrarydef inesclock tf orprocessor/CP U timemeasurements.

13 Writing Experimental Data from C

Instead of printing the result only on the screen, the C program can write it to
a file.
For example:
1 FILE * fp ;
2

3 fp = fopen ( " search . dat " , " w " ) ;

4

5 if ( fp == NULL )
6 {
7 printf ( " Error opening file .\ n " ) ;
8 return 1;
9 }
10

11 fprintf ( fp , " % d % f \ n " , n , time_taken ) ;

12

13 fclose ( fp ) ;

For multiple input sizes, the program can repeatedly write:

1 fprintf ( fp , " % d %.9 f \ n " , n , time_taken ) ;

6
 The resulting file may look like:

1000 0.000012
2000 0.000024
4000 0.000048
8000 0.000096
16000 0.000192

GNUplot can then read this file.

14 Important Timing Principle

Only the part of the program whose execution time is being studied should be placed
between the timing calls.
For example:
1 start = clock () ;
2

3 linearSearch (a , n , target ) ;
4

5 end = clock () ;

Do not include operations such as:

• printing the entire array,
• generating unrelated output,
• waiting for keyboard input,
• GNUplot commands.
inside the measured section.
The purpose is to measure the computational work of the algorithm as consistently
as possible.

15 Why Very Small Timings Can Be Unreliable

Searching or sorting a small array may execute so quickly that a single measurement
is very small.
For example:

0.000000 seconds
0.000001 seconds
0.000000 seconds

This does not mean that the algorithm requires zero time.
It means that the measured interval is very small relative to the available timer
resolution and other sources of measurement variability.
A practical approach is to repeat the algorithm many times and measure the total
time.
For example:
1 start = clock () ;
2

3 for ( int r = 0; r < repetitions ; r ++)

4 {

7
 5 linearSearch (a , n , target ) ;
6 }
7

8 end = clock () ;
9

10 time_taken =
11 ( double ) ( end - start ) / CLOCKS_PER_SEC ;
12

13 average_time = time_taken / repetitions ;

The value of repetitions should be selected so that the total measured interval
is sufficiently large for meaningful measurement.

16 Important Experimental Rule: Same Conditions

When comparing two algorithms, the experiment should be designed fairly.
For example, when comparing Linear Search and Binary Search:
• Use the same input sizes.
• Use the same machine and program compilation conditions.
• Use appropriate input data for each algorithm.
• Do not include input/output operations in the measured algorithm time.
• Repeat measurements when individual times are too small.
For Binary Search, the input array must be sorted.
When comparing sorting algorithms, an especially important rule is:

Use identical input data for all algorithms being compared.

For example:

Random array
|
+----> Bubble Sort
|
+----> Optimized Bubble Sort
|
+----> Insertion Sort
|
+----> Merge Sort

The algorithms should receive copies of the same original array.

Otherwise, differences in the input itself can affect the measured execution times.

17 Sorting Algorithm Data File

Suppose the C program compares:
• Bubble Sort
• Optimized Bubble Sort
• Insertion Sort
The data file can contain:

8
 # n Bubble OptimizedBubble Insertion
1000 0.012 0.009 0.006
2000 0.048 0.037 0.025
4000 0.191 0.150 0.099
8000 0.765 0.601 0.398

The columns are:

Column Meaning
1 Input size n
2 Bubble Sort time
3 Optimized Bubble Sort time
4 Insertion Sort time

The GNUplot command is:

1 set title " Sorting Algorithm Comparison "
2 set xlabel " Input Size ( n ) "
3 set ylabel " Execution Time ( seconds ) "
4 set grid
5

6 plot " sorting . dat " using 1:2 \

7 with linespoints title " Bubble Sort " , \
8 " sorting . dat " using 1:3 \
9 with linespoints title " Optimized Bubble Sort " , \
10 " sorting . dat " using 1:4 \
11 with linespoints title " Insertion Sort "

18 Plotting Merge Sort Along With Other Algorithms

If Merge Sort is also included:

# n Bubble Optimized Insertion Merge

1000 ... ... ... ...
2000 ... ... ... ...
4000 ... ... ... ...
8000 ... ... ... ...

then:
1 plot " sorting . dat " using 1:2 \
2 with linespoints title " Bubble Sort " , \
3 " sorting . dat " using 1:3 \
4 with linespoints title " Optimized Bubble Sort " , \
5 " sorting . dat " using 1:4 \
6 with linespoints title " Insertion Sort " , \
7 " sorting . dat " using 1:5 \
8 with linespoints title " Merge Sort "

9
 19 Saving a Graph as a PNG Image
An interactive plot is useful during development, but students may also need to save
the graph.
A PNG output can be generated using:
1 set terminal png
2 set output " sorting_plot . png "
3

4 set title " Sorting Algorithm Comparison "

5 set xlabel " Input Size ( n ) "
6 set ylabel " Execution Time ( seconds ) "
7 set grid
8

9 plot " sorting . dat " using 1:2 \

10 with linespoints title " Bubble Sort " , \
11 " sorting . dat " using 1:3 \
12 with linespoints title " Optimized Bubble Sort " , \
13 " sorting . dat " using 1:4 \
14 with linespoints title " Insertion Sort "
15

16 set output

The resulting file will be:

sorting_plot.png

The set output command without a filename closes the current output file.
GNUplot supports direct output to image and document formats, including PNG.

20 Using a GNUplot Script

Instead of typing every command manually, create a file such as:

sorting_plot.gp

with:
1 set terminal png
2 set output " sorting_plot . png "
3

4 set title " Sorting Algorithm Comparison "

5 set xlabel " Input Size ( n ) "
6 set ylabel " Execution Time ( seconds ) "
7 set grid
8

9 plot " sorting . dat " using 1:2 \

10 with linespoints title " Bubble Sort " , \
11 " sorting . dat " using 1:3 \
12 with linespoints title " Optimized Bubble Sort " , \
13 " sorting . dat " using 1:4 \
14 with linespoints title " Insertion Sort "
15

16 set output

10
 The script can then be executed from the Ubuntu terminal using:
1 gnuplot sorting_plot . gp

This is particularly useful when a graph needs to be regenerated after changing

the experimental data.

21 Complete Ubuntu Workflow

A typical directory may contain:

AOA/
|
+-- sorting.c
+-- [Link]
+-- sorting_plot.gp
+-- sorting_plot.png

Compile the C program:

1 gcc sorting . c -o sorting

Run it:
1 ./ sorting

Check the generated data:

1 cat sorting . dat

Run GNUplot:
1 gnuplot sorting_plot . gp

The graph should now be available as:

sorting_plot.png

22 Checking the Data Before Plotting

Students should inspect their data file before blaming GNUplot for an incorrect graph.
Use:
1 cat sorting . dat

Check that:
• the file exists;
• the input sizes are correct;
• the execution-time values are numeric;
• columns are separated consistently;
• there are no accidental text values in numeric columns.
GNUplot normally interprets whitespace-separated fields as separate data columns.
If a CSV file is used instead, the separator can be specified, for example:
1 set datafile separator " ,"

11
 23 Common GNUplot Commands
Command Purpose
plot "[Link]" Plot data from a file
using 1:2 Use column 1 as X and column 2 as Y
with points Plot points
with lines Plot connected lines
with linespoints Plot lines and points
title "..." Give the plotted curve a name
set title "..." Set graph title
set xlabel "..." Label X-axis
set ylabel "..." Label Y-axis
set grid Display grid lines
set key Enable the legend/key
unset key Disable the legend/key
set terminal png Select PNG output
set output "[Link]" Send output to a PNG file
set output Close the current output file

24 Searching Algorithm Experiment

For the Linear Search versus Binary Search experiment, use a data file such as:

# n LinearSearch BinarySearch
1000 0.000010 0.000002
2000 0.000020 0.000002
4000 0.000040 0.000003
8000 0.000080 0.000003
16000 0.000160 0.000004

The GNUplot script can be:

1 set terminal png
2 set output " s earch_ compar ison . png "
3

4 set title " Linear Search vs Binary Search "

5 set xlabel " Input Size ( n ) "
6 set ylabel " Execution Time ( seconds ) "
7 set grid
8

9 plot " search . dat " using 1:2 \

10 with linespoints title " Linear Search " , \
11 " search . dat " using 1:3 \
12 with linespoints title " Binary Search "
13

14 set output

The theoretical expectations are:

Linear Search: O(n)

and:

12
 Binary Search: O(log n)
The graph should be interpreted as experimental evidence, not as a mathematical
proof.

25 Sorting Algorithm Experiment

For Bubble Sort, Optimized Bubble Sort and Insertion Sort:
# n Bubble OptimizedBubble Insertion
1000 ...
2000 ...
4000 ...
8000 ...
16000 ...
The script is:
1 set terminal png
2 set output " so rt in g_ co mpa ri so n . png "
3

4 set title " Sorting Algorithm Comparison "

5 set xlabel " Input Size ( n ) "
6 set ylabel " Execution Time ( seconds ) "
7 set grid
8

9 plot " sorting . dat " using 1:2 \

10 with linespoints title " Bubble Sort " , \
11 " sorting . dat " using 1:3 \
12 with linespoints title " Optimized Bubble Sort " , \
13 " sorting . dat " using 1:4 \
14 with linespoints title " Insertion Sort "
15

16 set output

For random/average-case inputs, the expected asymptotic behavior is:

Algorithm Average-case complexity

Bubble Sort O(n2 )
Optimized Bubble Sort O(n2 )
Insertion Sort O(n2 )
The optimized Bubble Sort has a different best-case behavior because its early-exit
condition can terminate the algorithm after a pass when the input is already sorted.
This does not change its average-case complexity to O(n).

26 Merge Sort Experiment

If Merge Sort is included in the comparison:

Merge Sort = O(n log n)

for best, average and worst-case time complexity in the standard implementation.
A comparison data file may contain:

13
 # n Bubble OptimizedBubble Insertion Merge
1000 ... ... ... ...
2000 ... ... ... ...
4000 ... ... ... ...
8000 ... ... ... ...

and can be plotted using:

1 plot " sorting . dat " using 1:2 \
2 with linespoints title " Bubble Sort " , \
3 " sorting . dat " using 1:3 \
4 with linespoints title " Optimized Bubble Sort " , \
5 " sorting . dat " using 1:4 \
6 with linespoints title " Insertion Sort " , \
7 " sorting . dat " using 1:5 \
8 with linespoints title " Merge Sort "

27 Theoretical Complexity vs Experimental Graph

Students must distinguish between two different things.

Theoretical Complexity
Theoretical analysis asks:

How does the amount of computational work grow as n becomes large?

For example:

O(n), O(log n), O(n2 ), O(n log n).

Experimental Performance
The experiment measures actual execution time on a particular computer under particular
conditions.
The measured time can be affected by:
• processor speed;
• compiler and compiler options;
• operating-system activity;
• implementation details;
• input data;
• timer resolution;
• memory hierarchy and cache behavior;
• measurement methodology.
Therefore, an experimental graph will not normally be an exact mathematical curve
corresponding to the theoretical complexity.

14
 28 What the Graph Can and Cannot Tell You
A graph can help answer questions such as:
• Does execution time increase as n increases?
• Which of the tested algorithms is faster for the tested input sizes?
• Does one curve grow much faster than another?
• Does the observed trend appear consistent with theoretical expectations?
However, students should not conclude:

‘‘The graph proves that the algorithm is O(n2 ).’’

A finite set of measurements cannot by itself prove an asymptotic complexity result.

The correct conclusion is:

‘‘The experimental trend is consistent with the theoretical O(n2 ) behavior.’’

The theoretical complexity must come from algorithm analysis.

29 Do Not Compare Raw Times Without Context

Suppose the results are:

n Bubble Merge
1000 0.005 0.002
2000 0.020 0.004
4000 0.080 0.009

Bubble Sort appears to grow much faster.

This is consistent with:

O(n2 )
versus:

O(n log n).

However, the exact numerical values are specific to the experiment. They should
not be treated as universal execution times for the algorithms.

30 A Note About Logarithmic Axes

GNUplot can also use logarithmic axes, for example:
1 set logscale y

or:
1 set logscale xy

However, logarithmic plots are not required for the basic laboratory experiments.
Students should first understand ordinary linear-axis plots.
Do not use a logarithmic axis merely because the algorithm has O(log n) complexity.
A logarithmic axis changes how the numerical values are displayed; it does not
automatically ‘‘convert’’ an algorithm into a logarithmic complexity plot.

15
 31 Common Mistakes
Mistake 1: Wrong Column
If the data file is:

n bubble insertion
100 0.01 0.02
200 0.04 0.05

then:
1 using 1:2

plots Bubble Sort, while:

1 using 1:3

plots Insertion Sort.

Mistake 2: Forgetting the Legend

If several curves are plotted without titles, students may not know which curve represen
which algorithm.
Use:
1 title " Bubble Sort "

for each curve.

Mistake 3: Timing Input/Output

Do not measure:
1 printf ( " Sorted array = ... " ) ;

as part of the algorithm’s execution time.

Measure the algorithm itself.

Mistake 4: Using Different Random Arrays

When comparing sorting algorithms, do not generate a different random array for each
algorithm.
Generate one array and copy it:

original array
|
+----> copy 1 ----> Bubble Sort
|
+----> copy 2 ----> Optimized Bubble Sort
|
+----> copy 3 ----> Insertion Sort

Mistake 5: Concluding Complexity from One Data Point

One timing value cannot establish a growth pattern.
Use several input sizes.

16
Mistake 6: Using Very Small Input Sizes
If all execution times are extremely small, the graph may be noisy or unhelpful.
Increase the input size and/or repeat the algorithm multiple times.

Mistake 7: Confusing Big-O With Exact Runtime

Two algorithms can both be:

O(n2 )
while having different measured execution times.
Big-O describes asymptotic growth; it does not state that two implementations
will take the same amount of time.

32 Recommended Laboratory Procedure

For each algorithm-comparison experiment, follow this sequence.
1. Implement and test the algorithm for a small input.
2. Verify that the algorithm produces the correct result.
3. Choose several increasing values of n.
4. Generate the required input data.
5. For a comparison experiment, ensure that the algorithms being compared receive
equivalent/identical input data.
6. Measure the execution time.
7. Repeat measurements if individual timings are too small or noisy.
8. Write the results to a .dat file.
9. Inspect the file using:
1 cat filename . dat

10. Create a GNUplot script.

11. Plot the data using the correct columns.
12. Add a title, axis labels, grid and legend.
13. Save the graph as a PNG if required.
14. Compare the observed trend with the theoretical complexity.
15. Write a short conclusion explaining the observation.

33 Recommended File Organization

For the searching experiment:

search/
|
+-- search.c
+-- [Link]
+-- search_plot.gp
+-- search_plot.png

For the sorting experiment:

17
sorting/
|
+-- sorting.c
+-- [Link]
+-- sorting_plot.gp
+-- sorting_plot.png
This keeps the source code, experimental data, GNUplot script and generated graph
together.

34 Practice Exercise 1
Create a file named:
[Link]
containing:
100 0.01
200 0.02
300 0.03
400 0.04
500 0.05
Use GNUplot to:
1. plot column 1 against column 2;
2. add a title;
3. label both axes;
4. enable the grid;
5. display both points and lines.

35 Practice Exercise 2
Create:
[Link]
with:
100 0.01 0.02
200 0.02 0.04
300 0.03 0.06
400 0.04 0.08
500 0.05 0.10
Plot:
• column 2 as Algorithm A;
• column 3 as Algorithm B;
on the same graph.
Add:
• title;
• X-axis label;
• Y-axis label;
• legend;
• grid.

18
36 Practice Exercise 3
Modify a C sorting program so that it:
1. generates random input;
2. tests at least five different values of n;
3. measures execution time;
4. writes n and execution time to a .dat file.
Create a GNUplot graph from the resulting file.
The graph should contain:

X = Input Size
and:

Y = Execution Time.
Write three observations about the resulting graph.

37 Practice Exercise 4
Modify the previous experiment to compare two sorting algorithms.
Your data file should have the form:

n Algorithm_A Algorithm_B
...

Plot both algorithms on the same graph.

Answer:
1. Which algorithm is faster for the tested input sizes?
2. Does the difference increase as n increases?
3. What are the theoretical complexities of the two algorithms?
4. Is the observed trend consistent with the theoretical analysis?

38 Practice Exercise 5
Perform the Linear Search versus Binary Search experiment.
Your final data file should contain:

n LinearSearch BinarySearch

Generate a graph containing both curves.

Explain why the curves are expected to behave differently as n becomes large.
Remember that Binary Search requires a sorted array.

39 Final Checklist
Before submitting a GNUplot-based experiment, verify:
□ The C program produces correct results.
□ Several input sizes have been tested.
□ The algorithm execution time is measured separately from unrelated input/output
operations.

19
□ The comparison uses equivalent input conditions.
□ The .dat file contains valid numerical data.
□ Column 1 represents the input size.
□ The correct timing column is selected using using 1:2, using 1:3, etc.
□ The graph has a meaningful title.
□ Both axes are labelled.
□ Multiple curves have meaningful legend entries.
□ A grid has been added where useful.
□ The graph has been saved if required.
□ The experimental result is compared with, rather than confused with, theoretical
complexity.

Summary
1. GNUplot is used to visualize experimental data.
2. The C program is responsible for implementing the algorithm and measuring its
execution time.
3. A .dat file provides the data that GNUplot reads.
4. using 1:2 means ‘‘use column 1 for X and column 2 for Y.’’
5. Multiple curves can be plotted in one plot command, separated by commas.
6. title gives a curve its legend entry.
7. set xlabel, set ylabel and set title make the graph interpretable.
8. set output can be used to save a graph to a file.
9. Experimental timing is affected by the computer and measurement conditions.
10. A graph can support the observation that experimental behavior is consistent with
a theoretical complexity, but the graph itself is not a mathematical proof of
Big-O complexity.

20