image
박준수
Algorithms, 자바스크립트

[Coding Interview] Running Time Complexity

Runtime Complexity
- Describe the performance of an algorithm

 

How much more processing power/time is required to run your algorithm if we double the inputs?

 

Example1. String Reverse problem.

1
2
3
4
5
6
7
8
9
function reverse(str) {
  let reversed = '';
  for (let character of str) {
    reversed = character + reversed;
  }
  return reversed;
}
cs

 

abc -> cab

Each additional character = 1 step through 1 loop

This would be 'N', or 'linear' runtime

 

example 2. Steps

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function steps(n) {
  for (let row = 0; row < n; row++) {
    let stair = '';
    for (let column = 0; column < n; column++) {
      if (column <= row) {
        stair += '#';
      } else {
        stair += ' ';
      }
    }
    console.log(stair);
  }
}
cs

 

As 'n' increased by one, we had to do way, way more stuff, or (n*n) things total

 

This Would be N^2, or quadratic runtime

 

Types of Run Time Complexity

  1. Constant Time, 1: No matter how many elements we're working with, the algorithm/operation/whatever will always take the same amount of time
  2. Logarithmic Time, log(n): You have this if doubling the number of elements you are iterating over doesn't double the amount of work. Always assume that searching operations are log(n)
  3. Linear Time, n: Iterating through all elements in a collection of data. If you see a for loop spanning from '0' to 'array.length'. you probably have 'n', or linear runtime
  4. Quasilinear Time, n*log(n): You have this if doubleing the number of elements you are iterating over doesn't double the amount of work. Always assume that any sorting operation is n*log(n).
  5. Quadratic Time, n^2: Every element in a collection has to be compared to every other element. 'The handshake problem'
  6. Exponential Time, 2^n: If you add a "single" element to a collection, the processing power required doubles.

Big 'O' Notation

  1. O(n): Linear
  2. O(1): Constant
  3. O(n^2): Quadratic
  • Iterating with a simple for loop through a single collection? -> probably O(n)
  • Iterating through half a collection? -> Still O(n). There are no constants in runtime.
  • Iterating through two "Different" collections with separate for loops? -> O(n+m)
  • Two nested for loops iterating over the same collection? -> O(n^2)
  • Two nested for loops iterating over different collections? -> O(n*m)
  • Sorting? -> O(n*log(n))
  • Searching a sorted array? -> O(log(n))

 

 

Leave a Comment

ko_KRKorean
en_USEnglish ko_KRKorean