Cracking the Code with Time and Space Complexity

What is BIG O?

Big O is a way of comparing two sets of codes. Let's say code one and code two accomplish exactly the same thing. So how would we compare one against the other?

Code one might be more readable; code two might be more concise. Based on these two, any code could be better based on personal preference. But Big O is a way of comparing code one and code two mathematically about how efficiently they run. In a coding interview, you will absolutely be asked questions about Big O.

So let's look at what Big O is:

Let's say we have a stopwatch, and we run code one. We start the stopwatch, and it runs for 15 seconds. Then we reset the stopwatch and run code two, and code two runs a lot longer than 15 seconds. It runs for a full minute.

Based on this, we can say that code one is better than code two. We can measure it. This is called TIME COMPLEXITY.

The thing about time complexity that is interesting is that it is not measured in time. Because if you took the same code and ran it on a computer that runs twice as fast, it would complete twice as fast. It doesn't make the code any better. It just means the computer is better. So it is measured in the number of operations that it takes to show the output of the code.

SPACE COMPLEXITY:

Let's say code one, while it runs very fast comparatively, let's say it takes up a lot of memory when it runs. And code two, even if it takes a longer time, but may be it takes up less memory.

As a great software engineer, you decide if preserving memory space is your most important priority, and you don't mind having some extra time.

Decoding Omega, Theta, and O

When dealing with time, complexity, and space complexity, three Greek letters come into play: Omega (Ω), Theta (Θ), and Omicron (O). Omicron is better known as O in Big O.

Example:

Let's take a quick look at what each of these is used for. Consider a list with seven items [1,2,3,4,5,6,7], and imagine building a for loop to iterate through this list in search of a specific number.

- Best Case Scenario (Omega):

- If you're looking for the number one which is in the start of the list, this is your best-case scenario. You'll find it in one operation.

- Average Case Scenario (Theta):

- Now, if your target is the number four or any number which is somewhere in the middle, this is representing the average case, it requires a moderate level of iteration.

- Worst Case Scenario (Omicron or O):

- On the flip side, searching for the number seven. This is the worst-case scenario, requiring iteration through the entire list. The number of operations are greatest in this scenario.

In discussions about code efficiency, the best-case scenario is denoted by Omega (Ω), the average case by Theta (Θ), and the worst case by Omicron or O. You often hear people say, "Ok, that's your worst-case Big O. But what about your best case or your average case Big O?" Well, there is no direct best case or average case. Big O, technically, is either omega or theta. However, when discussing Big O, the focus is always on the worst case.