# How to Do a Worst-Case Run-Time Analysis We determine the worst-case running time of a program by totaling the costs associated with each operation in the program. The costs of operations follow a set of rules, which we outline first, followed by rules for combining costs. ## Costs of individual operations - Accessing a variable (in the environment) takes 1 step - Arithmetic (addition, multiplication, etc) and boolean operations (comparisons, and, or, etc) each take 1 step - Calling a function takes 1 step - Updating the value of a variable in the environment takes 1 step (for `=`), plus the time to compute the new value - Instantiating an object (e.g. `new LinkedList(capacity)` in Java) takes one step, plus the time to compute each input and the time it takes to run the constructor. If you are instantiating a built-in datatype, assume the cost is 1. Instantiating a record (e.g. `new SimpleList(first, null)`) takes one step, plus the time to compute each input. - Updating the value stored in a field in the heap takes 1 step for each location you have to follow to get to the right spot, plus the time to compute the new value. For example, - `myacct.balance = 100` takes 3 steps: 1 to access `myacct`, 1 to get to the `balancelocation`, and 1 for the `=`. There is no cost for using a number, boolean, or string - `custA.account.balance = 100` would take 4 steps: the extra step compared to the previous example is because we follow two locations (one per `.`) as compared to one in the previous example - Walking through all elements of a list (whether with recursion or a for-loop) takes a number of steps dependent on the length of the list. Since this isn’t known in advance, we introduce a variable for this size. Typically, we introduce a fresh variable for the size of each input whose size can vary. For example, if a function takes a list, we can give the length of the list the variable “N”. ## Costs of built-in functions - `map` and `filter` each take time proportional to the length of the list times the work done in the lambda function. Ignore the runtime of `.stream() `and `.collect(...)` when using `map` and `filter` in Java. - `length` on a list takes constant time (not proportional, for reasons we will see in week 3) - `append` on lists takes time proportional to the total lengths of the two lists - For our purposes, mathematical operations, such as `num-modulo`, take time 1 to run, plus the cost of the function call and the cost to compute/access the inputs. ## Combining costs Four rules guide how to combine costs for individual programming constructs into costs for an entire program: - if two **statements/expressions occur sequentially** (one after the other), add their costs - for an `if/else` **statement**, add the cost of computing the question to the larger cost of the `if` and `else` answers. - for a **loop**, multiply the size of the data (number of iterations) by the work that is done we do on each individual element - for a **recursive function**, we write the time it takes to run the function on an input of size N in terms of the time it takes to run the non-recursive code and the time it takes to run the recursive call (in terms of the recursive call’s input size). For instance, if we say that the time it takes to run the function is T(N), and the recursive call works on an input of one smaller, we would write T(N) in terms of T(N-1). We call this a **recurrence relation.** We can solve for the closed form of the time, or we can leave it as a recurrence relation. ## Keeping it simple: focus on the worst case In practice, we can’t predict the exact number of steps that will be taken in a program without knowing the exact input. For example, consider a program to check whether an item is in a list: for elt in some_list:   if (elt == data_to_find):     return True return False How many times will we perform the comparison check? It depends on where (if anywhere) the `data_to_find` is in the input list. How do we predict the cost of this code then? We will make a **worst-case assumption** that the `data_to_find` is not in `some_list`, and hence we will check every element. This is a sufficient approximation for many settings, and it is a more manageable way to get started thinking about costs. *** ## Annotating programs for run-time: for-loop in Python Here’s a concrete example of annotating each line of a program with its costs: count = 0                   # 1 (assign)             for elt in some_list:       # N   if (max(elt, 10) == 10)     # 1 (access elt) + 1 (max) + 1 (==)     count = count + 1         # 1 (access count) + 1(+) + 1 (assign) return count                # 1 (access count) Then, we total up the costs: **1 + (N \* (3 + 3)) + 1 = 6N + 2** ## Annotating programs for run-time: recursion in Java Here is some code doing the same computation, written using recursion in Java. Because it is recursive, we write it as a recurrence relation. Let’s call the cost of running `rFun` on an input of size N to be T(N). Then, int rFun(SimpleList someList):   if (someList == null) { // 1 (access) + 1 (==)     return 0;               // not the worst case   } else {     if (max(fst, 10) == 10) {  // 1 (access fst) + 1 (max) + 1 (==)       return 1 + rFun(someList.rest());       // 1 (+) + 1 (access someList) + 1 (call rest) + 1 (call rFun) + T(N-1) (rFun on rest)     } else {       return rFun(someList.rest());       // 1 (access rest) + 1 (call rFun) + T(N-1) (rFun on rest)     }   } Then, we total up the costs and write it as a recurrence: **T(N) = 2 + 3 + 3 + T(N-1)**      **= 8 + T(N-1)** *** ## Examples of recurrences We can start to see the pattern in recurrence relations by assuming that T(0) = C, that is, the cost of running a recursive function on an input of size 0 will be some constant cost C. Then, we can start to write down some iterative examples for common recurrence relations: ### T(N) = B + T(N-1) We have **T(0)  = C** **T(1)  = B + T(0) = B + C** **T(2)  = B + T(1) = B + (B + C) = (2 \* B) + C** **T(3)  = B + T(2) = B + ((2 \* B) + C) = (3 \* B) + C** **T(4)  = B + T(3) = B + ((3 \* B) + C) = (4 \* B) + C** The pattern that emerges is that **T(N) = (N \* B) + C**. ### T(N) = B + A\*N + T(N-1) We have **T(0) = C** **T(1) = B + A\*1 + T(0) = B + A + C** **T(2) = B + A\*2 + T(1) = 2 \* B + 3 \* A + C** **T(3) = B + A\*3 + T(2) = 3 \* B + 6 \* A + C** **T(4) = B + A\*4 + T(3) = 4 \* B + 10 \* A + C** It is a little harder to see the pattern here, but it turns out to be **T(N) = N \* B + (N^2 + N)/2 \* A + C** ### T(N) = B + T(N/2) Let’s assume that **T(1)** takes some time **K**. Then, **T(2)  = B + T(1) = B + K** **T(4)  = B + T(2) = 2 \* B + K** **T(8)  = B + T(3) = 3 \* B + K** **T(16) = B + T(4) = 4 \* B + K** The pattern is **T(N) = log2(N) \* B + K**, where **log2(N)** is the base-2 logarithm of N. *** ## When is one cost better than another? After using the rules to compute costs, we are left with cost summaries along the lines of - **_N \* 2 + 4_** - **_N \* 2 + 7_** - **_N + N + N + 8_** - **_N \* (N + 3) + 2_** - **_etc_** When should we say that one cost is worse than another? Technically, the costs in these expressions are getting worse from the first to the last expression. But do we really care about a difference of 3 operations (as between the first two) in the context of processing a large list? If the list were large enough, the cost of visiting every element is clearly more impactful than an extra operation here and there. In practice, we classify program costs by the nature of the function from the size of the input to the cost. Let’s recast our four examples as functions named **_T_** (for “time”): - **_T1(N) = N \* 2 + 4_** - **_T2(N) = N \* 2 + 7_** - **_T3(N) = N + N + N + 8_** - **_T4(N) = N \* (N + 3) + 2_** If we were to graph these functions over increasing values of N, we’d find that the first three yielded straight-line graphs (constant slopes), while the fourth curves upward over time. Back in high school, you learned terminology for functions based on the shapes of their graphs, such as “linear”, “quadratic”, and “exponential”. As a reminder, here’s a pictorial view:  _Linear (red), quadratic (blue), and exponential (green) growth \[image from_ [_Wikipedia_](https://en.wikipedia.org/wiki/Exponential_growth)_]_ In computer science, we typically describe the running times of programs in these terms. For example, for a list-membership function, we might say - member is linear or - member is in **_O(N)_** (where **_O(N)_** is the set of all functions whose growth is linear in the size of **_N_**.) Specifically, the terms you will see in computer science are: - constant – **_O(1)_** - logarithmic – **_O(log N)_** - linear – **_O(N)_** - **_O(N \* log N)_** \[serves as its own name] - quadratic – **_O(N^2)_** - exponential – **_O(2^N)_** _\[For those feeling rusty on logarithmic growth, it is the inverse of exponential growth, and grows much more slowly than linear. For a graphical representation, look at the top-left red/blue/green graph at this_ [_Wikipedia page on logarithmic scales_](https://en.wikipedia.org/wiki/Logarithmic_scale) _(about half way down on the right).]_ When we compare algorithms for time, the higher in this list an algorithm is classified in, the faster it will be as data gets large. We don’t worry about time comparisons for small data (they’ll be fast enough because the data are small). We worry about larger data. *** # Understanding Runtime Complexity in Java Runtime complexity refers to the amount of computational time taken by an algorithm to run, as a function of the length of the input to the program. It helps in analyzing the efficiency of an algorithm. Big O notation is a mathematical notation used in computer science to describe the performance or complexity of an algorithm. Specifically, it characterizes algorithms in terms of their worst-case or upper bound performance, focusing on their behavior when the input size grows towards infinity. :::success If you want to quiz yourself, see the bottom of this document! ::: :::danger Remember: Not everything in this document has to make sense right now. It will by the end of the course. ::: ## 1. Constant Time Complexity (O(1)) Constant time complexity denotes a scenario where the runtime of the algorithm does not depend on the input size. ### Example: Accessing an element from an array using an index. ```java public class ConstantTime { public static int getElement(int[] arr, int index) { return arr[index]; } public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5}; System.out.println(getElement(arr, 2)); // Output: 3 } } ``` ## 2. Linear Time Complexity (O(n)) Linear time complexity denotes a scenario where the runtime of the algorithm increases linearly with the increase in the size of the input. ### Example: Searching for an element in an array. ```java public class LinearTime { public static int linearSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; } } return -1; } public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5}; System.out.println(linearSearch(arr, 4)); // Output: 3 } } ``` ## 3. Quadratic Time Complexity (O(n^2)) Quadratic time complexity denotes a scenario where the runtime of the algorithm is proportional to the square of the size of the input. ### Example: Bubble sort algorithm. ```java public class QuadraticTime { public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } public static void main(String[] args) { int[] arr = {5, 3, 1, 4, 2}; bubbleSort(arr); for (int i : arr) { System.out.print(i + " "); // Output: 1 2 3 4 5 } } } ``` ## 4. Logarithmic Time Complexity (O(log n)) Logarithmic time complexity denotes a scenario where the runtime of the algorithm decreases by a constant factor with each step. ### Example: Binary search algorithm. See quiz question 5 for details. ```java public class LogarithmicTime { public static int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5}; System.out.println(binarySearch(arr, 4)); // Output: 3 } } ``` ## 5. Exponential Time Complexity (O(2^n)) Exponential time complexity denotes a scenario where the runtime of the algorithm doubles with each additional element in the input. ### Example: Naive recursive calculation of Fibonacci numbers. ```java public class ExponentialTime { public static int fib(int n) { if (n <= 1) { return n; } return fib(n - 1) + fib(n - 2); } public static void main(String[] args) { System.out.println(fib(10)); // Output: 55 } } ``` In this guide, each Java class demonstrates a different runtime complexity through a simple example. Understanding these basic runtime complexities is crucial for analyzing and optimizing the efficiency of your algorithms. --- ## Runtime Complexity Quiz (Arrays & Linked Lists) :::danger Test your understanding of runtime complexities concerning arrays and linked lists with the following questions: ::: <details> <summary>1. What is the time complexity of accessing an element in an array given its index?</summary> The time complexity of accessing an element in an array given its index is O(1) (constant time). This is because arrays have direct access to memory locations based on the index, which allows for immediate retrieval of the data stored at that index. </details> <br> <details> <summary>2. What is the time complexity of accessing an element in a linked list given its index?</summary> The time complexity of accessing an element in a linked list given its index is O(n) (linear time). Unlike arrays, linked lists do not have direct access to memory locations. To access an element at a particular index, you have to traverse the list from the head (or tail) node, one element at a time, until you reach the desired index. </details> <br> <details> <summary>3. Why does insertion at the beginning of a linked list take constant time (O(1)), while insertion at the end of an array can potentially take linear time (O(n))?</summary> Insertion at the beginning of a linked list takes constant time (O(1)) because it merely involves creating a new node and adjusting a couple of pointers which is a constant time operation regardless of the size of the linked list. On the other hand, insertion at the end of an array can potentially take linear time (O(n)) because if the array is full, a new larger array has to be created, all elements from the old array have to be copied to the new array, and then the new element can be added at the end. This operation involves copying n elements, which takes linear time. </details> <br> <details> <summary>4. What is the time complexity of searching for an element in an unsorted array?</summary> The time complexity of searching for an element in an unsorted array is O(n) (linear time). This is because, in the worst case, you may have to traverse the entire array to find the desired element, making the time complexity proportional to the size of the array. </details> <br> <details> <summary>5. What is the time complexity of searching for an element in a sorted array and why? Provide an example algorithm that achieves this time complexity.</summary> The time complexity of searching for an element in a sorted array can be O(log n) (logarithmic time) if a binary search algorithm is used. Binary search works by repeatedly dividing in half the portion of the array that could contain the target value, and comparing the target value to the middle element of that portion. If the target value is equal to the middle element, the position is returned. If the target value is less or greater, the search continues on the lower or upper half, respectively. The binary search algorithm reduces the problem size by half with each step, thus achieving a time complexity of O(log n). </details> <br> <details> <summary>6. Explain why the time complexity of deleting a node from a doubly linked list, given only access to that node, is O(1).</summary> The time complexity of deleting a node from a doubly linked list, given only access to that node, is O(1) because it involves constant time operations. You merely adjust the pointers of the adjacent nodes to bypass the node to be deleted. </details> *** _Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CSCI0200 document by filling out the_ [_anonymous feedback form_](https://docs.google.com/forms/d/e/1FAIpQLScDfGq8uaR2zXSc9wZTA83kfmM8N9UATB0RU0cGMfvJnmL5lQ/viewform)_._ ---