Linear Data Structures

What will be runtime complexity of the method when we’re going to add another loop before or after nested loops?

Once again, we can simplify this. The square of this number is always greater than the number itself. So in this expression, n squared always grows faster than N. So, we can drop n and conclude that this method runs in O(n^2).


Arrays – we use them to store a list of items sequentially.
Arrays are the simplest data structures, and we use them to store a list of items, like a list of strings, numbers, objects, and literally anything. These items get stored sequentially in memory. For example, if you allocate an array of five integers get stored in memory like this.

Let’s say the address of the first item in memory is 100. As you probably know, integers in Java take four bytes of memory, so the second item would be stored at the memory location 104, third item would be stored at the memory location 108, and so on. For this very reason, looking up items in an array by their index is super fast. We give our array an index and it will figure out where exactly in memory it should access. So if you need to store a list of items and access them by their index, arrays are the optimal data structures of you.
Now what do you think is the runtime complexity of this operation? Lookup O(1) because the calculation of the memory address is very simple. It doesn’t involve any loops or complex logic.
Let’s look at the limitations or weaknesses of arrays in Java and many other languages. Arrays are static, which means when we allocate them, we should specify their size, and this size cannot change later on. So we need to know ahead of time how many items we want to store in an array. Now, what if we don’t know? We have to make a guess. If our guess is too large, we’ll waste memory because we’ll have cells that are never filled. If our guess is too small, our array gets filled quickly. Then to add another item, we’ll have to resize the array, which means we should allocate a larger array and then copy all the items in the old array into the new array. This operation can be costly.

Can you guess the runtime complexity of this operation? Let’s say our array has five items. Now we want to add a 6^th item. You have to allocate a new array and copy all these five items into that new array. So the runtime complexity of this operation is