| Hi! Search for "Big O notation" on Google. In this case, the O refers to roughly how complex an algorithm is, or how much time it takes to compute the answer. n is the size of the input to the problem. For example, if we are searching for a word through a large Charles Dickens book, we are working on an O(n) problem, where n is the number of pages in the book. We say that this problem has an "order of n" time complexity. This means that if we double the number of pages in the book to 2 * n, the problem will simply take twice as long. All O(n) problems have this property. If you multiply n by a constant size (e.g., 2), the time it takes to complete the problem will be multiplied by that same constant size. Some problems are harder. For example, we have two long books, and want to see if there is a sentence in Book 1 that also appears in Book 2. Since you have a tech background, you'll realize that an easy solution to this is to write a for loop nested within a for loop. This type of problem is O(n^2), because the time it takes to solve the problem scales with the square of the problem size. If I double the number of pages of each book (n), the problem actually takes four times as long! So this problem is O (order) of n^2 (number of pages). If you read up on Big O notation, you'll learn that some problems can be solved really fast. We call this O(1) or constant time (since 1 is a constant). For example, if I ask you to tell me if a number is even or odd, you can tell me in constant time, no matter how big an integer I give you (i.e., you just look at the last digit and ignore the rest of the ginormous number). Some problems are harder.... O(n^3) or even O(n * (n-1) * (n-2) * ... * 3 * 2 * 1). Good luck! |