Time Complexity

Time complexity is not the actual time taken, it is the “amount of time taken as a function of input size”.

When talking about time complexity, we generally talk in terms of “worst cast scenarios”, when the input size is closer to millions or even billions, because only in that case, would the performance of our algorithm be tested thoroughly.

We use the Big O notation ( O(n), O(nlogn), O(n!)) to denote the time complexity of an algorithm, this is also called the “upper bound” of an algorithm. E.g say we have an algorithm with time complexity of O(n) so in the worst case scenario, it will only run n operations and no more than that, which is the upper bound of this algorithm

Say we are studying an algorithm and we figure out that if we graph the function w.r.t the input size, we get a function like: $f (n) = 12 n^{2} + 7 n + 32$

In order to figure out the time complexity we have to follow the steps below:

remove all the constants, which leaves us with: $f (n) = n^{2} + n + 1$
when worst case scenario comes, the biggest term in the equation will start dominating the result, so we just have to figure out which is the biggest term in the quation, which is $n^{2}$
so the time complexity for this algorithm would be: $O (n^{2})$

Just like Big O notation there are many other notations our there to represent varios scenarios:

Big O $O (n)$ - worst case scenario (upper bound)
Big Theta $θ (n)$ - average case scenario
Big Omega $Ω (n)$ - best case scenario (lower bound)

But most of the times, we only need Big O notation to grasp the effectiveness of an algorithm.

Space Complexity

Just like time complexity, it is the “amount of space taken as a function of input size”

Say we are working on an algorithm that takes in an array of n elements as an input, so the input size would be n, and it must return an array with the squares of those numbers. Since the size of the output array is equal the size of the input array, it means that the space complexity of this algorithm is linear, which means that it increases linearly with the input size. The space complexity would be $O (n)$

For an algorithm that takes in an array and returns the sum of all the numbers in that array, the space complexity would be $O (1)$ because no matter how big the input array is, we would just be returning a single sum each time, hence the space complexity will be independant of the input size.

Most of the times, we give more importance to time complexity as compared to space complexity, because in the modern age, getting more space for computation has become relatively cheaper and easier, so most of our focus in now on figuring out efficient and “faster” ways of doing things.

Dyanmic Array

These are very self explanatory. Think of dynamic arrays as boxes that increase in size as the number of elements in them grows.

We can use the following struct to implement dynamic arrays in C

typedef struct {
  void *data;
  size_t element_size;
  size_t len;
  size_t capacity;
} Vector;
 
Vector create_vector(size_t element_size) {
  Vector vec;
  vec.data = NULL;
  vec.element_size = element_size;
  vec.len = 0;
  vec.capacity = 0;
  return vec;
}

Here we just define the generic pointer void* data which points to the actual elements in the array, the element_size is the size of single element of that array, len is the total length of the array at any time, and capacity is the total number of elements that can be stored in the array at any given time. When we create a new vector, all we have to do is speficy the size of element that we want to use this vector to store. Initially, the data in of the vector will point to NULL as we don’t have any elements yet, and the size and capacity of the vector both will be zero.

The vector operations that we need to implement for this to be a minimal usable implementation are: push, pop, and get

push

void resize_vector(Vector *vec, size_t new_capacity) {
  void *new_data = realloc(vec->data, vec->element_size * new_capacity);
  if (!new_data || new_data == NULL) {
    printf("memory allocation failed during resize\n");
    exit(SYS_EXIT);
  }
  vec->data = new_data;
  vec->capacity = new_capacity;
}
void vector_push(Vector *vec, const void *input_data) {
  if (vec->len == vec->capacity) {
    size_t new_capacity = vec->capacity == 0 ? 1 : vec->capacity * 2;
    resize_vector(vec, new_capacity);
  }
 
  void *target_mem = (char *)vec->data + (vec->element_size * vec->len);
  memcpy(target_mem, input_data, vec->element_size);
  vec->len += 1;
}

Along with implementing push operation we have to implement a resize operation for the vector as well in order to actually allow the array to be dynamic.
The resize operation is rather simple, we provide a pointer to an already existing vector along with a size to which we want the vector to be resized to. Then we reallocate the memory of the vector’s data field but this time we match it to the new_capcity that we have provided, so the total memory that would be allocated would be element_size * new_capacity. If the reallocation was a success that we set the newly allocated memory to vector’s data field and change the vector capacity to the new_capacity.
After that the push operation is rather easy to understand, we first of all do a bounds check, if the length of the vector is already equal to the capacity of the vector then we just resize the vector to double its current size.

void *target_mem = (char *)vec->data + (vec->element_size * vec->len);`

This line basically gets the memory at first empty location inside the vector, and after then just copy the memory from input_data onto this location and just increase the length of the vector by 1.

pop

int vector_pop_back(Vector *vec, void *pop_buffer) {
  if (vec->len == 0) {
    return 0;
  }
  vec->len -= 1;
  if (pop_buffer != NULL) {
    void *last_element = (char *)vec->data + (vec->element_size * vec->len);
    memcpy(pop_buffer, last_element, vec->element_size);
  }
  return 1;
}

The pop operation takes in the vector which we wanna pop and the pop_buffer, it is basically the pointer to an element that you want the last element to be popped into. So the usage would be something like:

any_type pop_buffer;
vector_pop(&some_vector, &pop_buffer);

For the pop operation, firstly we just check if the vector is empty, if it is we return 0 which means the pop failed, if the vector is not empty, then we decrement the length of the vector and get the last element of the vector.

NOTE: if you are wondering that we should be using vec->len - 1 instead of vec->len to get the last element, right before the get the last element, we did vec->len -= 1 which automatically makes the length of the vector equal to the index of the last element

Then we check if the user provided a proper buffer to pop into, if yes then we just copy the memory from the last_element into the pop_buffer and just return 1 for a successful pop

get

void *vector_get(Vector *vec, size_t index) {
  if (index >= vec->len) {
    return NULL;
  }
  return (char *)vec->data + (vec->element_size * index);
}

For get operation, the user provides the pointer to the vector along with the index of the element they want, then if the element does not exist in the vector, we return NULL but if it does, then we just return the pointer to that element.

NOTE: one thing to keep in mind is that this pointer is only valid for immediate use, if say after using this get operation the vector gets resized, this pointer will become invalid

free

Another operation that we can implement is the free_vector operation, which as it’s name suggests, just frees the memory of the vector after we don’t need it.

void free_vector(Vector *vec) {
  free(vec->data);
  vec->data = NULL;
  vec->len = 0;
  vec->capacity = 0;
};

It is important to free the memory that we no longer need. This operation just frees the memory of the data field and resets all the other fields.

bookshelf

Explorer

Data Structures and Algorithms

Time Complexity

Space Complexity

Dyanmic Array

push

pop

get

free

Table of Contents