Week 02 Tutorial Notes

Recursion and Analysis of Algorithms

Group Question

Break off into groups and answer the following questions about this function.

If you get stuck ask your tutor for hints and help!

#include <stdio.h>
#include <string.h>

// str is a string
void func(char *str) {
	for (int i = 0; i < strlen(str); i++) {
		printf("%c\n", str[i]);
	}
	printf("Done\n");
}

/*
The function might be called like so:
char *greeting = "Hello, World!";
func(greeting);
*/
  1. What is the input to the function?
    • When analysing time complexity, what does \(n\) represent?
    • What changes as \(n\) increases?
  2. Now that we know what \(n\) is, let's figure out the time complexity of the function:
    • How long does each line take to execute?
    • What is the time complexity of strlen() when called once?
    • What is the overall time complexity of the function?
  3. Running this function with \(n\) = 1,000,000 takes roughly 10.503s.
    • Explain why the function takes so long to run.
    • What can we change to make the function run faster?
    • What is the time complexity now?

The input is the given string. \(n\) represents the length of the string (i.e., the number of characters in the string).

For example, if the string is "Hello, World!", then \(n = 13\).

The length of the string gets longer as \(n\) increases.

Analysing each line we get the following.

#include <stdio.h>
#include <string.h>

void func(char *str) {
	for (int i = 0 /* 1 */; i < strlen(str) /* n(n + 1) */; i++ /* n */) {
		printf("%c\n", str[i]); // n
	}
	printf("Done\n"); // 1
}

The time complexity of strlen() depends on the implementation. There are two ways to figure this out.

  1. Analyse the code yourself.
  2. Read the documentation / google the time complexity of the library function.

In this case, strlen() counts characters in the string until it reaches a \0 byte. Therefore calling the strlen() once is \(O(n)\).

Adding up all the terms in program we get:

$$ \begin{align} & 1 + n(n + 1) + n + n + 1 \\ &= n^2 + 3n + 2 \\ &= O(n^2) \end{align} $$

Therefore the overall time complexity is \(O(n^2)\).

For every iteration of the loop strlen() is being called. Which means the program needs to recount how many letters are in the string before printing the next character. This is effectively a nested for loop.

How can we make this faster? Since the length of the string doesn't change we should calculate the length once and store it in a variable.

#include <stdio.h>
#include <string.h>

// str is a string
void func(char *str) {
	int length = strlen(str); // O(n)

	for (int i = 0; i < length; i++) { // O(n)
		printf("%c\n", str[i]);
	}
	printf("Done\n");
}

This is now \(2n = O(n)\). Which is much faster for large values of \(n\)!

When \(n=1,000,000\) this now takes 0.018s to execute! Instead of 10.503s.