Big O Notation and Time Complexity Part 5

This past week has been very productive and I’ve learned a lot with BIG O. We are almost finishing this series and will continue blogging about other technologies or techniques to become a better programmer. let us dive into the next example for time complexity, exponential time.

O(2^n) — Exponential time

Exponential (base 2) running time means that the calculations performed by an algorithm double every time as the input grows. We are going to use the Power Set example.

Power Set: finding all the subsets on a set.

To understand the power set, let’s imagine making a pizza. You have many toppings to choose from, like pepperoni, mushrooms, and bacon. Let’s call each topping A, B, C. What are your choices? You can choose one topping, or two or all of them, and so on. The power set gives you all the possibilities.

lets view the examples:

powerset('') // =>  ['']
powerset('a') // => ['', 'a']
powerset('ab') // => ['', 'a', 'b', 'ab']

Did you notice any pattern?

• The first returns an empty element.
• The second case returns the empty element + the 1st element.
• The 3rd case returns precisely the results of the 2nd case + the same array with the 2nd element b appended to it.

Notice that every time the input gets longer, the output is twice as long as the previous one.

this is the code for the example above:

function powerset(n = '') {
  const array = Array.from(n);
  const base = [''];

  const results = array.reduce((previous, element) => {
    const previousPlusElement = previous.map(el => {
      return `${el}${element}`;
    });
    return previous.concat(previousPlusElement);
  }, base);

  return results;
}
powerset('a, b, c')

I’m using reply to reproduce the code and obtain the results.

[
  '',       'a',    ',',     'a,',    ' ',      'a ',    ', ',
  'a, ',    'b',    'ab',    ',b',    'a,b',    ' b',    'a b',
  ', b',    'a, b', ',',     'a,',    ',,',     'a,,',   ' ,',
  'a ,',    ', ,',  'a, ,',  'b,',    'ab,',    ',b,',   'a,b,',
  ' b,',    'a b,', ', b,',  'a, b,', ' ',      'a ',    ', ',
  'a, ',    '  ',   'a  ',   ',  ',   'a,  ',   'b ',    'ab ',
  ',b ',    'a,b ', ' b ',   'a b ',  ', b ',   'a, b ', ', ',
  'a, ',    ',, ',  'a,, ',  ' , ',   'a , ',   ', , ',  'a, , ',
  'b, ',    'ab, ', ',b, ',  'a,b, ', ' b, ',   'a b, ', ', b, ',
  'a, b, ', 'c',    'ac',    ',c',    'a,c',    ' c',    'a c',
  ', c',    'a, c', 'bc',    'abc',   ',bc',    'a,bc',  ' bc',
  'a bc',   ', bc', 'a, bc', ',c',    'a,c',    ',,c',   'a,,c',
  ' ,c',    'a ,c', ', ,c',  'a, ,c', 'b,c',    'ab,c',  ',b,c',
  'a,b,c',  ' b,c', 'a b,c', ', b,c', 'a, b,c', ' c',    'a c',
  ', c',    'a, c',
  ... 28 more items
]

The input was larger this time and the result shows the algorithm ran 42 times showing 128 elements.

I will see you next week with another example. happy coding.