Challenge #8 – The Big O Problem

30 October 2019 Solved Twig Intermediate

It’s time to get algorith­mic­al” and solve a prob­lem that could eas­ily be imple­men­ted using a poorly per­form­ing algorithm the per­form­ant way.

Chal­lenge

The chal­lenge is quite straight­for­ward. For each of the entries in a struc­ture, out­put the the title of the entry and its ancest­ors in a bread­crumb man­ner. So for example giv­en the fol­low­ing structure:

Entry 1
    Entry 2
        Entry 3
        Entry 4
    Entry 5
Entry 6
    Entry 7

The out­put should be:

Entry 1
Entry 1 > Entry 2
Entry 1 > Entry 2 > Entry 3
Entry 1 > Entry 2 > Entry 4
Entry 1 > Entry 5
Entry 6
Entry 6 > Entry 7

The catch is that the algorithm should have a com­plex­ity of O(1), mean­ing that the runtime, and in our case the num­ber of data­base quer­ies, should remain con­stant regard­less of how many entries exist in the struc­ture. If, on the oth­er hand, the num­ber of data­base quer­ies grows lin­early and is pro­por­tion­al to the num­ber of entries then your algorithm has a com­plex­ity of O(n).

This is called Big O nota­tion” and can be visu­al­ised as follows:

Big O Notation

For a more in-depth explan­a­tion check out A Sim­pli­fied Explan­a­tion of the Big O Nota­tion by Kar­una Sehgal.

If you learn bet­ter from stor­ies about car­ri­er pigeons and lawn mow­ing then you can watch the first few minutes of this fun video.

Rules

The algorithm should be writ­ten in twig using Craft tags, so using the {% nav %} tag is allowed. It must out­put a structure’s entries as described above with a com­plex­ity of O(1). It should not rely on any plu­gins and the code will be eval­u­ated based on the fol­low­ing cri­ter­ia in order of priority:

  1. Read­ab­il­ity
  2. Brev­ity
  3. Per­form­ance

There­fore the code should be read­able and easy to under­stand. It should be con­cise and non-repet­it­ive, but not at the expense of read­ab­il­ity. It should be per­form­ant, but not at the expense of read­ab­il­ity or brevity.

Tips

You can keep track of how per­form­ant your algorithm is by turn­ing on the debug tool­bar on the front-end of your site and keep­ing an eye on the num­ber of data­base quer­ies required to out­put the struc­ture. Get a baseline by out­put­ting the struc­ture entries without their ancest­ors, then see how many extra quer­ies are neces­sary to out­put the titles of their ancest­ors. If the num­ber of data­base quer­ies increases as you add more entries to the struc­ture then you’re likely work­ing with a O(n) algorithm. If it remains con­stant then con­grat­u­la­tions, you have achieved O(1)!

Debug Toolbar DB

Solution

Submitted Solutions

  • Alex Roper
  • Prateek Rungta
  • Sarah Schütz
  • David Hellmann