BigO Flashcards
Identify the space and time complexity of algorithms
[Reverse String] What is the space and time complexity for this code?
function reverseString(str) {
return str.split('').reverse().join('');
}
Space Complexity: O(n). It creates a new array from the string, hence the space used scales linearly with the input size.
Time Complexity: O(n). The function iterates through each character of the string once for splitting, reversing, and joining.
[Paldindrome Check ] What is the space and time complexity for this code
function isPalindrome(str) {
return str === str.split('').reverse().join('');
}
Space Complexity: O(n). Similar to reversing a string, it creates an array which scales with the length of the string.
Time Complexity: O(n). It involves the reversal of the string (O(n)) and a comparison which is also O(n) in the worst case.
[Anagram Check] What is the space and time complexity for this code?
function areAnagrams(str1, str2) {
const charMap = s => s.split('').sort().join('');
return charMap(str1) === charMap(str2);
}
Space Complexity: O(n). It stores sorted versions of both strings, requiring space proportional to the length of the strings.
Time Complexity: O(n log n). Sorting each string takes O(n log n) time, and comparing two sorted strings takes O(n) time, making the dominant factor O(n log n).
[Binary Search] What is the space and time complexity for this code?
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Element not found
}
Space Complexity: O(1). The function uses a fixed amount of extra space.
Time Complexity: O(log n). Each step halves the search space, leading to logarithmic time complexity.
[Sliding Window Technique] What is the space and time complexity for thi
function maxSubarraySum(arr, size) {
let maxSum = 0;
let tempSum = 0;
if (arr.length < size) return null;
for (let i = 0; i < size; i++) {
maxSum += arr[i];
}
tempSum = maxSum;
for (let i = size; i < arr.length; i++) {
tempSum = tempSum - arr[i - size] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}
Space Complexity: O(1). The function only uses a fixed amount of extra space regardless of the input size.
Time Complexity: O(n). The function iterates through the array once, making it linear in time complexity.
[Linear Search] What is the space and time complexity for this code?
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}
Space Complexity: O(1). It uses a constant amount of space.
Time Complexity: O(n). It may need to check each element in the array once.
[Factorial] What is the space and time complexity for this code?
function factorial(n) {
if (n === 0 || n === 1) {
return 1;
}
return n * factorial(n - 1);
}
Space Complexity: O(n). Due to recursion, it consumes space on the call stack proportional to the input size.
Time Complexity: O(n). The function calls itself n times.
[Bubble Sort] What is the space and time complexity for this code?
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
Space Complexity: O(1). It sorts the array in place, using only a small, constant amount of additional space.
Time Complexity: O(n^2). It contains nested loops, each potentially iterating n times.
[Fibonacii Sequence] What is the space and time complexity for this code
function fibonacci(n) {
let fib = [0, 1];
for (let i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
Space Complexity: O(n). It stores the Fibonacci sequence up to n.
Time Complexity: O(n). It calculates each Fibonacci number once.
[Insertion Sort] What is the space and time complexity for this code?
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
Space Complexity: O(1). Sorts in place, using constant space.
Time Complexity: O(n^2). Nested iterations over the array in the worst case.
[Counting Sort] What is the space and time complexity for this code?
function countingSort(arr, max) {
let countArray = new Array(max + 1).fill(0);
let output = new Array(arr.length);
// Counting the frequency of each element
for (let i = 0; i < arr.length; i++) {
countArray[arr[i]]++;
}
// Accumulating counts
for (let i = 1; i <= max; i++) {
countArray[i] += countArray[i - 1];
}
// Placing elements into the correct position
for (let i = arr.length - 1; i >= 0; i--) {
output[countArray[arr[i]] - 1] = arr[i];
countArray[arr[i]]--;
}
return output;
}
Space Complexity: O(k). Requires additional space for the count array, where k is the range of the input values.
Time Complexity: O(n + k). Iterates over the input array and the count array.
[Sum of Array] What is the space and time complexity for this code?
function sumArray(arr) {
return arr.reduce((acc, val) => acc + val, 0);
}
Space Complexity: O(1). It uses a constant amount of additional space.
Time Complexity: O(n). It iterates through each element of the array once.
[Find minimum and maximum] What is the space and time complexity for thi
function findMinMax(arr) {
let min = arr[0];
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
return { min, max };
}
Space Complexity: O(1). Only uses a fixed number of variables.
Time Complexity: O(n). It goes through the array once to find min and max.
[Remove duplicates] What is the space and time complexity for this code?
function removeDuplicates(arr) {
return Array.from(new Set(arr));
}
Space Complexity: O(n). The Set object may hold all elements if they are unique.
Time Complexity: O(n). The construction of the Set object iterates through all elements once.
[Find Majority element] What is the space and time complexity for this c
function findMajorityElement(arr) {
let count = 0;
let candidate = null;
for (let num of arr) {
if (count === 0) {
candidate = num;
}
count += (num === candidate) ? 1 : -1;
}
return candidate;
}
Finds the element that appears more than half the time in the array
Space Complexity: O(1). Uses a fixed amount of extra space.
Time Complexity: O(n). Iterates through the array once.
