Given what we've covered in the last few chapters, try to evaluate the time and space complexity of the following problems. With time and practice, you'll start to recognize the time and space complexity of the code you write on your own.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
for (let i = 0; i < n; i++) {
console.log("Hello!");
}
}
The time complexity of the function test is O(N) because the loop runs n times, where n is the input size. The number of iterations directly scales with the input size.
The space complexity of the function test is O(1) because it does not use any additional space outside of the input size.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
console.log("Hello!");
}
}
}
The time complexity of test is O(N^2). Although the inner loop's number of iterations decreases with each iteration of the outer loop, the total number of operations still grows quadratically with n.
The space complexity is O(1) as no additional space proportional to n is used.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
let result = [];
for (let i = 0; i < n; i++) {
result.push(i);
}
return result;
}
The time complexity is O(N) because the loop runs n times.
The space complexity is also O(N) as the result array grows linearly with the input size n.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
let sum = 0;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= i; j++) {
sum += 1;
}
}
return sum;
}
The time complexity is this problem is O(N^2) as we have two nested loops.
Unlike the previous problem, the space complexity is O(1). The sum variable holds an integer value so there is no additional space used that grows with n.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
let result = [];
for (let i = 0; i < n; i++) {
result.push(i);
for (let j = 0; j < n; j++) {
result[i] += j;
}
}
return result;
}
The time complexity is O(N^2) due to the nested loop structure, where both loops run n times.
The space complexity is O(N). Note that in the inner loop, we are not adding new values to the result array but we are modifying existing values. This is why the space complexity is not O(N^2).
What is the time complexity of the function test? What is its space complexity?
function test(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
console.log("Hello!");
}
}
}
}
The time complexity is O(N^3) due to the three nested loops each running n times.
The space complexity is O(1) as no extra space is used that grows with n.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
let result = [];
for (let i = 0; i < n; i++) {
result.push(new Array(n).fill(0));
}
return result;
}
The time complexity is O(N^2) due to the creation of n arrays, each of size n.
The space complexity is also O(N^2) as the result array grows quadratically with the input size, holding n arrays of size n.
Let's explore the time complexity in detail:
n times, where n is the input size.
n is created and filled with zeros. The new Array(n).fill(0) operation itself consists of two parts:
O(1) operation since it essentially allocates memory for n elements but doesn't initialize them.
.fill(0) method operates linearly with respect to the size of the array it's filling. This part of the operation is O(n) because it involves setting each of the n elements in the newly created array to 0.
In summary, for each iteration of the loop, an array is created (O(1)) and then filled (O(n)). The dominant operation here is the filling of the array, which is O(n). Since this operation is repeated n times, the total time complexity is O(N^2).
Now the space complexity:
result variable is an array that grows as new arrays are pushed into it.
n iterations of the loop adds a new array of size n to the result array.
n arrays, each containing n elements. Therefore, the total space used is proportional to n * n elements. Thus, the space complexity is O(N^2), as the space required grows quadratically with the input size n.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
for (let i = n; i >= 1; i /= 2) {
console.log("Hello!");
}
}
The time complexity is O(logN) because the loop divides the value of i by 2 in each iteration. The number of iterations is determined by how many times i can be divided by 2 before reaching 1.
The space complexity of the function test is O(1) because it does not use any additional space.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
let matrix = [];
for (let i = 0; i < n; i++) {
matrix[i] = [];
for (let j = 0; j < n; j++) {
matrix[i][j] = i + j;
}
}
return matrix;
}
The time complexity of the function test is O(N^2) because it involves two nested loops, each running n times. As a result, the number of operations is proportional to n * n = n^2.
The space complexity is also O(N^2) because it creates a matrix of size n * n. The space required grows quadratically with the input size.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
for (let i = 0; i < n; i++) {
for (let j = 1; j < n; j *= 2) {
console.log("Hello!");
}
}
}
The time complexity is O(NlogN) because it involves two nested loops. The outer loop runs n times, and the inner loop doubles the value of j in each iteration. Thus, the inner loop runs logN times. The total number of operations is proportional to N * logN.
The space complexity of the function test is O(1) because it does not use any additional space.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < 100; j++) {
console.log("Hello!");
}
}
}
The time complexity is O(N) because the outer loop runs n times and the inner loop runs a constant 100 times. The constant factor does not affect the overall time complexity.
The space complexity of the function test is O(1) because it does not use any additional space.
What is the time complexity of the function test? What is its space complexity?
function test(n, m) {
for (let i = 0; i < n; i++) {
console.log("Hello!");
}
for (let j = 0; j < m; j++) {
console.log("World!");
}
}
In this example, we have two separate loops, one iterating n times and the other iterating m times. The time complexity of the first loop is O(N), and the time complexity of the second loop is O(M). Since the loops are iterating over different collections, we cannot directly combine or simplify their time complexities.
Therefore, the time complexity is expressed as O(N) + O(M). This notation emphasizes that the time taken by the algorithm increases linearly with the size of n and m separately.
Remember that if the values of n and m are not related or do not have a fixed relationship, we cannot further simplify the time complexity expression.
Space Complexity is still O(1) as we are not using any additional space.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
for (let i = 0; i < 2 * n; i++) {
console.log("Hello!");
}
}
Although the loop runs 2n times, we can simplify the time complexity by removing the constant factor. Therefore, the time complexity is O(N).
Space Complexity is O(1) as we are not using any additional space.
What is the time complexity of the function test? What is its space complexity?
function test(n) {
let count = 0;
for (let i = n; i > 1; i = Math.floor(i / 2)) {
for (let j = 0; j < n; j++) {
count++;
}
}
return count;
}
The time complexity is O(NlogN). The outer loop runs logN as it halves i in each iteration. The inner loop runs n times so the overall time complexity is O(logN) * O(N) or O(N*logN).
Space Complexity is O(1) as we are not using any additional space.