Big O

Question 1

Big O notation

function findFirstIndexOfNumber(number, array) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === number) {
      return i;
    }
  }
  return -1
}

Answer 1

O(N)

Linear time

Question 2

Big O notation

function compareArrays(array1, array2) {
  let arrayOfPairs = [];
  array1.forEach(function(e, i) {
    array2.forEach(function(e2, i2) {
      if (e === e2) {
        arrayOfPairs.push([i, i2]);
      }
    });
  });
  return arrayOfPairs;
}

Answer 2

O(A*B)

Question 3

Big O notation of inserting in an array

Answer 3

O(1)

constant time

Question 4

Big O notation

def binarySearch(arr, l, r, x):
 
    # Check base case
    if r >= l:
 
        mid = l + (r - l) // 2
 
        # If element is present at the middle itself
        if arr[mid] == x:
            return mid
 
        # If element is smaller than mid, then it
        # can only be present in left subarray
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)
 
        # Else the element can only be present
        # in right subarray
        else:
            return binarySearch(arr, mid + 1, r, x)
 
    else:
        # Element is not present in the array
        return -1
 

Answer 4

O(logn)

Let’s look at binary search as an example, In binary search, we are looking for an example x in an N-element sorted array.

We first compare x to the midpoint of the array. If x — middle, then we return. If x < middle, then we search on the left side of the array. If x > middle, then we search on the right side of the array.

We start off with an N-element array to search. Then, after a single step, we’re down to “/i elements. One more step, and we’re down to H/t, elements. We stop when we either find the value or we’re down to just one element.

The total runtime is then a matter of how many steps (dividing N by 2 each time) we can take until N becomes 1.

Question 5

Big O notation

int f(int n) {
 if (n <= 1) {
 return 1;
 }
 return f ( n - 1) + f { n - 1);
 }

Answer 5

O(N)

When you have a recursive function that makes multiple calls, the runtime will
often (but not always) took likeO(branchest ! e p t , 1), where branches is the number of times each recursive call branches. In this case, this gives us 0( 2”).

The space complexity of this algorithm will beO(N). Although we haveO(2N) nodes in the tree total, only
0(N) exist at any given time.Therefore, we would only need to haveO(N) memory available.

Question 6

Big O notation

void foo(int[] array) {
 int sum = 0;
 int product = 1;
 for (int i = 0; i < array.length; i++) {
 sura += array[i];
 }
 for (int i = 0; i < array.length; i++) {
 product *= a r r a y [ i ] ;
 
System.out.println(sura + ", " + product);
 }

Answer 6

O(n)

n + n = 2n

We can drop the constants, so the answer is O(n)

Question 7

Big O Notation

void p r i n t U n o r d e r e d P a i r s ( i n t [ ] array) {
 for (int i = 0; 1 < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
 System.out.println(array[i] + "," + array[j]);
 >
 >
 }

Answer 7

O(n^2)

Question 8

Big O Notation

 void printUnorderedPairs(int[] arrayAj intjj arrays) {
 for (int i = 0j i < arrayA.length; i++) {
 for (int j = 0; j < arrayB.length; j++) {
 for (int k = 0; k < 160800; k++) {
System.out.println(arrayA[i] + "," + arrayB[j]);
 }

 }
 }

Answer 8

O(A*B)

The loop that goes through 160800 items is in constant time.

Question 9

Which of the following are equivalent to 0(N)?Why?

• 0(N + P), where P < M
• 0(2N)
• 0(N + l o g N)
• 0(N + M)

Answer 9

O(2N)

• Since we drop constants
• Not logn since O(N) dominates logn

Question 10

Suppose we had an algorithm that took in an array of strings, sorted each string, and then sorted the full
array. What would the runtime be?

Answer 10

0 ( a * s ( l o g a + l o g s ) )

Let’s define new terms—and use names that are logical.
* Let S be the length of the longest string.
* Let a be the length of the array.

Now we can work through this in parts:
* Sorting each string isO(s l o g s),
* We have to do this for every string (and there are a strings), so that’s 0( a * s l o g s).
* Now we have to sort all the strings. There a re a strings, so you’ll may be inclined to say that this takes 0( a
l o g a) time. This is what most candidates would say. You should also take into account that you need
to compare the strings. Each string comparison takes 0 ( s ) time.There are 0 ( a l o g a) comparisons,
therefore this will takeO(a*s l o g a)time.
If you add up these two parts, you get 0 ( a * s ( l o g a + l o g s ) ) .
This is it. There is no way to reduce it further

Question 11

Big O Notation of a balaced binary tree

int sum(Node node) {
if (node == null) {
 return 0;
 }
 return sum(node,left) + node.value + sum(node.right);
}

Answer 11

O(N)

once and does a constant

This code touches each node in the tree and doesnt loop.