Is It Really Quantum Computing

Following various discussions during the week on quantum computing, triggered by the news that NASA and Google have bought a DWave system, I wrote a piece for Scientific American on the debate that seems to continue about whether DWave's systems are really a quantum computer.

You can read the full piece here.

The Real Phone Hacking Scandal

As part of the launch in the UK of the magazine The Conversation, I wrote a piece to discuss the security of mobile devices is an increasingly important part of the cyber security equation.

You can read the full article here.

NASA & Google Team Up To Explore Quantum Computing

On Thursday 16th May 2013 I appeared on BBC Radio 4's Material World programme with Dr Geordie Rose, Chief Technical officer at D-Wave Systems, the company who developed this computer, and to discuss whether the DWave system is quantum computing or not. You can hear the programme here.

The discussion was triggered by the news that one of these "quantum" computers is to be installed at NASA's Ames research centre. It will be shared between Google, NASA, and researchers via the Universities Space Research Agency, providing access to a machine which is up to 3600 times faster than a conventional computer.

Unintended Consequences Of Connecting "Everything"

For me, one of the most important areas of cyber security is that relating to SCADA systems, and other related Industrial Control Systems. To help raise awareness I wrote a piece for the Scientific American website.

You can read the full article here.

Exploding the urban myths about how to stay safe online

In response to some previous articles, I became aware of many comments that suggested that there are a set of urban legends growing about how one can stay safe online.  In order to try to correct the worst of these myths I wrote a piece for the BBC.

See the full article here.

Picture This - Secrets Lost Before Your Eyes

A picture is said to be worth a thousand words. Today, businesses wanting to guard against the potentially serious hazard of vitally important data being maliciously leaked to unauthorised people outside or even inside the organisation, need to get to grips with an alarming reality: a picture can also conceal a thousand words.

More than enough, at any rate, to betray all your most precious and commercially sensitive data. You name it: locations of newly-discovered oil fields; formulae for synthesising newly-discovered molecules of breakthrough drugs costing millions to develop; designs of revolutionary products you’re planning on being the first to bring to market; ultra-sensitive lists of hard-won customers; or whatever else.

Data concealed in pictures? If it sounds like science-fiction or the basis of a plot sequence in the next Mission Impossible movie, maybe it is. But unfortunately for organisations, that doesn’t make the threat any less dangerous.

Wax Tablets Used For Writing In Roman Empire

The technique is called steganography, from the Ancient Greek words meaning ‘hidden’ or ‘covered’ writing’, just as that lumbering dinosaur the stegosaurus is so named because its back was covered in those large bony plates whose real purpose is a mystery even today.

Steganographia Published circa 1499

But steganography wasn’t a mystery to the Ancient Greeks; indeed they most likely invented it. The Greek historian Herodotus records that in 312 BC, Histaeus of Miletus commanded the head of his most trusted slave to be shaved and tattooed with a vitally important secret message on it. Once the slave’s hair had grown, hiding the message, Histaeus used him as an emissary to a friendly power via enemy territory to instigate a revolt against the Persians. 

This example from history shows why steganographic writing is such a dangerous threat to security. Friends who betray us are always a more potent threat than people who we recognise as enemies from the outset, and steganographic messages look friendly and innocent. You could devise a simple steganographic message by agreeing with your recipient that your real message will consist of the first letter of every word of your apparent message. ‘Bring us your invoice by Monday’, for example, would really mean ‘BUY IBM.’

In steganographic writing the apparent message is known as the covertext and the real message is called the plaintext. The innocuous appearance of the covertext in the example illustrates why steganographic writing doesn’t tend to set alarm bells ringing. It looks innocent, whereas the message ‘BUY IBM’ encrypted in a simple code that consisted, say, of substituting each letter for the next letter in the alphabet - ‘CVZ JCN’ - obviously looks dodgy and would be certain to awaken the suspicions of even the most credulous member of an organisation’s industrial espionage prevention team.

The point is that any encrypted message will tend to raise suspicions because even though it can’t readily be read you will know it’s been encrypted and will instantly conclude that something fishy’s going on.

In the highly competitive ocean of modern business, the threat of steganography has recently become a major issue in corporate life. It’s been important for several years due to the increased computing power available on everyone’s desktop, but people have been distracted by publicity about cryptography and steganography has rather remained in the background. It’s a particularly worrying threat now because of the enormous computing power on desktops today, the massive volume of electronic communications, and the number of freely available tools that allow even a routine user to employ steganographic techniques.

The Film Character Gordon Gekko

By far the biggest threat is the potential for concealing steganographic writing within computerised images. With Windows you can literally drag and drop your hidden text onto a picture and the deed is done. As Gordon Gekko reminded us in the film Wall Street (1985), the most valuable commodity of all is information. And it’s precisely that which can so easily be given away today - or sold - using image-based steganographic techniques.

But what is actually happening when you carry out what looks like a simple drag and drop?

Closeup Of Pixels On  Laptop Screen

An electronic image is comprised of thousands of ‘picture elements’ or ‘pixels’. A pixel is a binary number that provides information on the colour or (in a black and white picture) the shade of grey that should be displayed in that particular pixel. The binary number will look something like this: 10011011 etc depending on the pixel in question. The individual numbers (the ‘1’ or the ‘0’) are known as ‘bits’ and the further along you go to the right the less significant the bits become in defining the precise colour of the pixel.

The opportunity for steganography occurs because the less significant bits towards the right can be changed without a significant change to the appearance of the pixel in the image. Indeed, there will probably not be any discernible change at all. But every time a bit is changed slightly a piece of data can be hidden in that changed bit. In a computerised image whose size is 256 by 256 pixels, making a total of 65,536 pixels, there would easily be room to conceal say, about 5,000 words of data.

Bit twiddling is the most common way to conceal text within a computerised image. There are many more techniques, though, particularly when using image formats such as the now ubiquitous ‘jpeg’ which many will have encountered through their digital cameras.

And so an apparently innocuous picture of - say - an employee’s child’s first day at school taken with a standard family digital camera could easily be used to conceal a leak that turns out to be so fatal to the organisation that by the time that school term ends, thousands of other mums and dads at the business from which the information was leaked have had to find new jobs - if they can.

What’s the best way to guard against the hazard of modern image-based steganographic betrayal? The first step is to recognise that it is a potential problem and get help to understand what tools are likely to available to a malicious team member. You also need to know the manner in which these tools can be used because not only is it hard to find the results of what the tools do but the tools themselves often leave little trace of their presence – some are even termed ‘zero footprint’ because they are.

Yet there is some help at hand because, just as those who have been building the steganography tools have released them onto the internet, a dedicated team of experts have been making available tools to help detect hidden messages through the science of ‘steganalysis’. Or perhaps it would be better to call steganalysis an art. The trouble is that the methods of detecting where and when steganogaphy has been used tend to rely on statistical techniques, and these by their very nature deal in probabilities rather than certainty. This means that the detection tools can, and do, give ‘false positives’. You may accuse a trusted employee of sending hidden confidential information only to find that it was, after all, only a picture of their child’s first day at school.

The detection tools need to be used so that the appropriate steganalysis tool is used in the appropriate situation. Admittedly, this is not easy, when the range of steganography tools and the steganalysis counterparts have proliferated and are proliferating just as the threat from viruses did when they first emerged into the IT environment.

Taking the threat of betrayal by apparently innocuous pixels seriously will lead you to put into the measures necessary to defend against it. And you do need to take this threat very seriously indeed. The stegosaurus may be long extinct, but steganographic treachery is, unfortunately, here to stay.

Will There Be An Industrial Revolution In Computing?

The year 1991 saw the successful conclusion of one of the most remarkable enterprises in the history of invention. A team of engineers at the London Science Museum managed to complete the construction of a cogwheel computer that had first been designed, but never built, 170 years earlier by the Victorian scientist and mathematician, Charles Babbage (1791-1871).

During his lifetime, Babbage insisted that his cogwheel brain, which he named the Difference Engine, was capable of being constructed and would have worked if it had been. His efforts to build it, however, met largely with ridicule, and Babbage died a disappointed man in 1871.

Why couldn’t Babbage build a Difference Engine in his lifetime? Today, with the benefit of hindsight, we know that the biggest problem which stymied him was the lack of a precision metal industry. It wasn’t that the overall design of his machine was faulty, or that cogwheels can’t be computer components (they can, though there’s no denying that electronic components do the job a whole lot better.)

Modern Build Of Babbage's  Difference Engine

The successful modern initiative to build a Difference Engine deliberately made use of components that were no more precisely-engineered than Babbage himself could have produced for individual cogwheels back in the nineteenth century. However, the 4,000 components - most of them cogwheels needing to be fashioned to be as much alike as possible - were manufactured for the modern build using modern industrial manufacturing processes which ensured consistent high quality components to a standard pattern. This was the result of the difference between the small-scale ‘craftsman’ approach for building precision components that Babbage was obliged to adopt, and the modern ‘industrial’ method used by the Science Museum’s engineers.

Charles Babbage

Today, despite his ultimate failure, Charles Babbage is regarded as the father of computing. His reputation continues to increase in direct proportion to the increasing importance of the computer in our high-tech age. It was somehow highly appropriate that in the year 2000, Microsoft’s former technology director, Nathan Myhrvold, took personal delivery of a full-scale modern-built Difference Engine. This was the second such machine ever built. Myhrvold had sponsored the construction of a second machine so that it could become the ultimate conversation piece in his home.

In the arcane world of cogwheel computing, the 170-year battle between the crafts approach and the industrial approach to making components for Babbage Engines was decisively won by the industrial approach. Today, in the enormously important and influential business of computer software development - a business which, in a very real sense, has made the modern world possible - the craftsman-like way of doing things has prevailed for a long time. But the day of the craftsman-like approach may be coming to an end, to be replaced by an industrial way of designing software that is faster, less risky, less expensive and more efficient.

Spining Mule At Beginning Of Industrial Revolution

The whole point of an ‘industry’ is that it brings a concerted and methodical approach to the task of creating something or putting raw materials through a particular process to achieve a final result. A key definition of ‘industry’ in the Shorter Oxford English Dictionary is ‘systematic work or labour’.

Cogwheels in Babbage's Difference Engine

But in so many cases, software development is not systematic. Instead, it is a strangely haphazard matter, involving methods, approaches and outputs that bear far more resemblance to the brilliant but ill-equipped genius Babbage painstakingly struggling with a few hired craftsmen to manufacture precisely-made cogwheels, than anything resembling a modern industry. No wonder the track record of success of modern software development is so, well, unsuccessful.

What about people who might say, ‘all right, anybody can criticise the modern software development business, but the fact of the matter is that enough projects have been completed, and have delivered enough of the functionality that was required, for the world we live in to be an enormously different place from what it was even just twenty years ago, let alone in Babbage’s time.’

This is, admittedly, a fair point, and certainly there is no denying that despite the shortcomings of the software development business, the products of software development obviously do provide significant value to the organisations that commission them, and the users who benefit from them.

Even as I write, software is being used around the world to control, monitor and make safe literally millions of processes that not even such a far-sighted technological prophet as Babbage could have come close to foreseeing. Drilling taking place ten miles below the ground, civilian and military aircraft flying ten miles above the ground or much higher, and all the myriad intricate visible and invisible processes that make the modern world what it is, are all enormously dependent on the power, precision and reliability of computer software.

But does this mean that we should be complacent about the effectiveness of modern software development techniques? Certainly not. Instead, all it means is that despite the ever-present practical, logistical and financial problems relating to software development today, computer software remains so much valued that, by and large, the organisations paying for software development projects are willing to suffer large risks and losses in order to obtain the benefits which software development can offer them.

Ten or even fifteen years ago, the risk factors attaching themselves to software development were much the same as they are today. Indeed I remember that back in the early 1990s the figure of 16 percent of problem-free software development projects was bandied about much as it is nowadays.

Can things ever get better?

The general sense of dissatisfaction with the way software is usually developed has been felt keenly since at least the mid-1980s. From time to time there have been false dawns of new ways of doing things; new ways that were supposed to constitute revolutionary improvements in how software was designed. However, in most cases the false dawns barely survived to lunchtime.

Object-orientated programming (OOP), for example, was supposed to introduce a new way of managing software development by basing programs around certain ‘objects’ - a bundle of features associated with a particular application - that could in principle be regularly re-used as and when required to facilitate rapid software development. But whilst OOP is widely used it didn’t fulfil its wider promise; it was more a question of oops! because developers didn’t find the objects as helpful as the original author initially hoped would be the case. Most developers concluded that the level of modification and customisation of the objects necessary was simply too great for the objects to be useful; so they wound up building their software from scratch instead. Albeit using OOP techniques.

A Reusable Class In UML

More progress has been won in recent years from new kinds of tools which, rather than seeking to revolutionise software development, aim instead to make developers more productive. A particularly useful tool here has been application development frameworks (ADFs). These are a form of open-to-all software packages that facilitate rapid customisation of the software for a particular application to the precise requirements of the organisation in question. But even ADFs are really still a set of generic building blocks, with the objective of being used across a wide variety of applications.

Today, the reason why software development is such a laborious and potentially risky and fraught matter is that the way in which software is designed means that opportunities to re-use code (ie. pre-written programs) is still extremely low. Software development mainly takes place using generic programming languages that render every project essentially a bespoke one. There has been limited infrastructure and markets that have encouraged developers to supply potentially re-useable programming components. But maybe re-use of pre-packaged functionality wasn’t the way to do it after all and a different perspective was required.

That different perspective was hoped to be a concept known as the domain-specific language (DSL). A DSL is a special kind of language designed to be used for a particular application or solution. It is not a new concept to computer scientists but it is one that has only really caught ion over the passed 10 years.

As one might imagine, a DSL will be all the more useful the more tightly the particular application or solution to which it caters is focused, because this will tend to increase the likelihood that another programmer, building a solution to a similar problem, will be able to use the same features of the language to specify what it is s/he wants the computer to do.

In fact some DSLs have relatively wide domain remits (eg. retail banking) while others have narrow remits (eg. operation of a retail banking ATM network). Incidentally, Microsoft has recently developed a special kind of DSL whose particular domain is helping developers to design other DSLs! It is now be possible for organisations (or their suppliers) to define languages aimed specifically at providing solutions for problems within their business domain. I doubt even Babbage would have thought of that.

DSLs create the possibility of a software ‘factory’. What is a software factory? A software factory is not some form of business or a special type of organisation.  In essence, it is a set of tools, a development environment if you will, that is optimised for building solutions in a particular business domain.  Hence, a software factory could be used by a traditional software supplier (assuming he adopts the new tools and techniques) or an organisation’s own internal IT department if they are developing applications for that organisation.

A software factory provides solutions not through using pre-written code or following best practice for a particular type of solution (although these can be a part of it) but through the use of a programming language (a DSL) that is inherently designed to write computer solutions to particular types of problems.

Software factories are most emphatically not about selling software packages that provides a one-size-fits-all solution to a particular problem. Instead, software factories acknowledge that everyone may want a different type of product but, to use analogy, if a factory is optimised to build motorcars is not suited for building houses.

1871 Machine Enabling Reproducible Screws

Despite allowing individual solutions to be provided, the software factory offer reliable ways to develop applications rapidly, relatively inexpensively and with lower risk than is seen using the generic programming languages and tools. One can make a direct comparison here with the introduction, in the mid nineteenth century, of standardised and precisely-milled mechanical components by the great mechanical engineer Joseph Whitworth, whose components and machine tools won international renown for their supreme accuracy in a repeatable format. The impact was felt not only in the form of Whitworth being the only supplier of these items, but also that his gospel of precision encouraged everyone to think about solving particular problems using tools built to common standards.


The ultimate aim for software factories is to remove much of the small-scale ‘crafts’ element from routine software development and confine such craftsmanship to the really sharp end of the most demanding software development initiatives. This will allow software development to become less expensive, lower risk and far more reliable while still giving organisations all the scope they need to establish and maintain a competitive advantage from their software.

A software factory, in other words, would offer the best of all possible worlds. However, it is a solution that is still struggling to find its place.  I suspect we are yet to see the full potential of software factories realised.  Or maybe they are impractical for other reasons: why learn to work in a specific factory when you can have a generic skill that can be moved to any employer.

I think what will happen over time is that this approach (or something similar) will begin to attract more business oriented people, and they will start to undertake work in their business domain that was only previously undertaken by specialist programmers. Maybe we will start to see a wider acceptance that with the right tools anyone can be creative when developing computer systems.

Beware The Watering Hole

Like any field science or engineering, information security (infosec) is littered with three letter abbreviations (TLAs) and buzzwords.  In infosec we also like to try to name the various types of attacks.  We hope that these are done using an analogy to make it clear the essence of the attack but sometimes, whilst it can help describe the essence of the attack, it can miss some important detail.

One important type of attack that has been coined recently is the "Watering Hole Attack".  The idea was that it was supposed conjure up visions of lions waiting at the watering hole for their prey.

Typically, these are taregtted atatcks as opposed to the scatter gun method used in many phishing attacks. Hence, it is used against groups of people who are quite resistnt to phishing attacks.

The attack assumes that the attacker can place some form of malware on alegitimate site.  Not a trivial task, but with enough research an atatcker can find a soft target which many of the target group use.  That soft target is easier to compromise that the mainstream systems that the group use.

Here I've tried to give a high level description of how these attacks work. The key steps in an attack are:

1. The victim visits a compromised website
2. This website, typically through an injected JavaScript element, redirects the visiting browser to an exploit site.
3. This exploit site checks what software the visiting machine is running and runs a suitable exploit.  One of the most successful exploits relied upon a vulnerability in Java.

The basic modus operandi of the attack is not unique. Drive-by downloads use something similar by redirecting to exploit sites using, for example, IFrames.

However, the psychology behind it's success is subtle . It works on the basis that individuals will naturally trust, and as a group we develop strong trust, even when something is outside our group.

I suspect that we'll hear more of this style of attack, and that it will become a major theme in the attacks over the coming year.

The Key To Public Key Encryption

I've talked several times about how quantum computers could cause a problem for RSA based public key encryption as, using Shor's algorithm, you can theoretically factor large numbers in timescales short enough to render the encryption pointless.  However, conventional computers can be used to factor.  There are several algorithms that can be implemented.  Below I've tried to flag up the main algorithms that have been developed. 

First, let's revisit the RSA algorithm. In RSA each user generates a key pair (one public and one private).  This is done by:

Graph of GCDs

1. Randomly select two large prime numbers: p and q;
2. Calculate the modulus: n=p*q
3. Randomly choose an encryption key e such that 1 < e < φ(n) where the greatest common divisor (gcd) of e and φ(n) = 1 and φ(n) = (p-1)(q-1) where φ(n) is known as the Euler's totient.

From this you can find the decryption key d by solving the equation: -e * d = 1 (mod φ(n)) and 0 ≤ d ≤ n. Then the user publishes their encryption key as {e, n} and keeps the decryption key {d, p, q} secret.

First 1000 Values of φ(n)

For Alice to encrypt a message m to Bob, she needs only {e, n} and then computes c=m^e (mod n) where 
0 ≤ m < n and Bob needs then only to compute m = c^d (mod n).







To attack RSA you typically take one of three approaches:

1. Factor n = p*q and hence compute φ(n) and thence d; or
2. Determine φ(n)  directly (without factoring) and thence d; or
3. Determine d directly

Current opinion suggests (although I am not aware of any proofs) that each is as computationally difficult as the other. It is factoring that has the greatest number of algorithms as they have evolved over the entire history of mathematics not just since its use in cryptography.

The factoring algorithms general considered are when factoring large numbers for attacks on RSA are:

Pierre de Fermat

1. Fermat's difference of squares: this dates from 1643. We find that any composite n = r * s can be expressed as  [(s+r)/2]²  - [(s-r)/2]² from which Fermat showed that by calculating y² - n using a specific sequence of y based upon n (easily calculated), you will find eventually find a perfect square from which you find s and r. The maximum number of steps needed to find the perfect square is (n - 2)/2 minus the largest integer less than or equal to square root of n
2. Euler's factoring method: Euler extended Fermat's method.  Euler noted that for some n two squares were equivalent in modulo n.  This allowed Euler to modify Fermat's approach slightly and sieve the results to reduce the number of values examined. 
3. Kaitchik's method: as late as 1945 Kraitchik revisited Fermat's approach and found a further representation where the difference of squares was a multiple of n,  allowing further sieving of results. It is the basis of the quadratic sieve.

   

   Leonhard Euler

4. Pollard's P-1 method: this relies upon the fact that for one of the primes p, the number p -1 has only small prime factors. An RSA designer would try to avoid this situation so as to avoid Pollard's attack but often the primes are chosen randomly and this check may not be made.
5. Pollard's rho method: published just one year after his p -1 method, the rho method was published. It is based upon the Floyd cycling algorithm, also called the tortoise and hare algorithm as it has two pointers which sieve through the results but at different speeds.  It also uses the fact that for larger numbers there is a greater than 50% chance that numbers can have a form of equivalence in modulo arithmetic when there is a particular relationship between the numbers, rather like the idea of "collisions" that leads to the birthday paradox.

   

   An Early "Sieve" For Finding Primes

6. Quadtratic sieve: this was developed in the 1980s. It essentially a means of trying to set up equivalences of squares in modulo n plus a means of storing primes so that hey can be compared rapidly.It does rely upon a type of trial an error but stores useful results for comparison later in the algorithm.
7. General number field sieve: this s fastest factoring algorithm we currently have. It relies upon choosing polynomials  that have a common root related to n.  The efficiency of the algorithm depends very much on the choice of polynomials and there no known method for optimally choosing these.  Hence, whilst the quadratic sieve can be the fastest algorithm it is not always reliably so.  Hence, the quadratic sieve is often used inside. 

6th Order Polynomial

There is still much work to be done on factoring large numbers into constituent primes.  It is deeply mathematical but it does have some profound consequences for public key encryption.  Hence, although you may not be interested in understanding the detail, it is worth having an appreciation of what techniques continue to be developed in factoring large numbers.

Although it has been studied for hundreds of years, and despite our modern computing power, for numbers more than 100 bits there is still scope for improvement in algorithm design.  Research continues to be published and will continue I believe until we have access to a working quantum computer.

Big-O

When testing out a lecture I’m due to give next month to non-computer scientists, I suddenly realised that the "Big-O" notation is not something generally understood. So, I thought a short introduction might help. Not least because anyone who wants to learn about computer science will run across its use almost immediately.

Big-O and three other related notations were introduced by Paul Bachmann and Edmund Landau. Hence, this set of notations bear the name “Bachmann–Landau Notations”, or alternaively “asymptotic notations”.

Big-O is used to write an equation like this:

f(x) = O( g(x) )

This means that the function f(x) bounded by a multiple of g(x). How the function is ultimately bounded depends upon the direction in which one is taking the limit of x. For example, consider the case of x going to infinity (the most common case). We write this as: f(x) = O( g(x) ) as x → ∞ if there exist positive constants C and M such that f(x) ≤ C g(x) for all x > M.

The second notation is the Ω notation. If again x tends to infinity we write this as: f(x) = Ω( g(x) ) as x → ∞ if there exist positive constants C and M such that f(x) ≥ C g(x) for all x > M.

When we write f(x) = Θ( g(x) ) it means that f(x) = O( g(x) ) whilst also f(x) = Ω( g(x) ).

The third notation is ο (Greek omicron). The omicron notation is also called "little-o" notation. Little-o is used like this: f(x) = ο( g(x) ) if the limit as x → ∞ of f(x)/g(x) is 0.

Finally we have the notation ω (lower-case Greek omega) which is used like this: f(x) = ω( g(x) ) if the limit as x → ∞ of f(x)/g(x) is ∞.

When we do not have x → ∞ technical details of the definitions differ slightly:

• f(x) = O( g(x) ) as x → k if there exist positive constants δ and C such that f(x) ≤ C g(x) for all x such that |x - k| < δ.
• f(x) = Ω( g(x) ) as x → k if there exist positive constants δ and C such that f(x) ≥ C g(x) for all x such that |x - k| < δ.
• f(x) = ο( g(x) ) as x → k if there if the limit as x → k of f(x)/g(x) is 0.
• f(x) = ω( g(x) ) as x → k if there if the limit as x → k of f(x)/g(x) is ∞.

Often you will see statements such as f(x) = O( g(x) ) without reference to an explicit limit and will have to determine from context what limit is implied.

Although Big-O is the most commonly used notation in computer science, the Ω and Θ notations are more commonly used in computer science than in mathematics. Little-o and ω notation is rarely used.





Visuaisation of Quick Sort Algorithm

In the theoretical analysis of algorithms it is common to estimate their complexity in the asymptotic sense ie to estimate the complexity as the input tends to infinity. The reason asymptotic estimates are used is because different implementations of the same algorithm may differ in efficiency. However, the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor called a “hidden constant”.

For example, the so called “quick sort” algorithm runs in a time proportional to the size of the list being sorted multiplied by the logarithm of the length of the list being sorted where the size of the list tends to infinity. In Big-O notation we write this as O(nlog(n)).