Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 9 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 5 chapters
Show chapters Hide chapters

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

2. Complexity
Written by Jonathan Sande

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Will it scale?

This age-old question is always asked during the design phase of software development and comes in several flavors. From an architectural standpoint, scalability is how easy it is to make changes to your app. From a database standpoint, scalability is about how long it takes to save or retrieve data in the database.

For algorithms, scalability refers to how the algorithm performs in terms of execution time and memory usage as the input size increases.

When you’re working with a small amount of data, an expensive algorithm may still feel fast. However, as the amount of data increases, a costly algorithm becomes crippling. So how bad can it get? Understanding how to quantify this is an important skill for you to know.

In this chapter, you’ll look at the Big O notation for the different levels of scalability in two dimensions: execution time and memory usage.

Time Complexity

For small amounts of data, even the most expensive algorithm can seem fast due to the speed of modern hardware. However, as data increases, the cost of an expensive algorithm becomes increasingly apparent. Time complexity measures the time required to run an algorithm as the input size increases. In this section, you’ll go through the most common time complexities and learn how to identify them.

Constant Time

A constant-time algorithm has the same running time regardless of the input size. Consider the following:

void checkFirst(List<String> names) {
  if (names.isNotEmpty) {
    print(names.first);
  } else {
    print('no names');
  }
}
Wega Fobi E(0)
Judypeqk mubu

Linear Time

Consider the following snippet of code:

void printNames(List<String> names) {
  for (final name in names) {
    print(name);
  }
}
Fohu Giko A(x)
Komiat deta

Quadratic Time

More commonly referred to as n squared, this time complexity refers to an algorithm that takes time proportional to the square of the input size. Consider the following code:

void printMoreNames(List<String> names) {
  for (final _ in names) {
    for (final name in names) {
      print(name);
    }
  }
}
Zizu Mepe O(s ) 7
Loisgelof fowu

Logarithmic Time

So far, you’ve learned about the linear and quadratic time complexities where each element of the input is inspected at least once. However, there are scenarios where only a subset of the input needs to be inspected, leading to a faster runtime.

const numbers = [1, 3, 56, 66, 68, 80, 99, 105, 450];

bool naiveSearch(int value, List<int> list) {
  for (final element in list) {
    if (element == value) return true;
  }
  return false;
}

bool betterSearch(int value, List<int> list) {
  int start = 0;
  int end = list.length;

  while (start < end) {
    final size = end - start;
    int middle = start + size ~/ 2;

    if (list[middle] == value) {
      return true;
    } else if (list[middle] < value) {
      start = middle + 1;
    } else {
      end = middle;
    }
  }

  return false;
}
Lexa Qaki U(qeh b)
Wovukujwneq giko

Quasilinear Time

Another common time complexity you’ll encounter is quasilinear time. Quasilinear time algorithms perform worse than linear time but dramatically better than quadratic time. You can think of quasi-linear as “kind of” like linear time for large data sets. An example of a quasilinear time algorithm is Dart’s sort method.

Kiqe Wuva U(v weg g)
Maamiyoluod fexa

Comparing Time Complexities

Take a look at how the time complexities compare to each other for large data sets:

U(h ) Teba Foye 4 I(f vug l) O(6) I(s) E(pul r)
Nupu tekid suwi bodgpuhaxiiy

Other Time Complexities

The five time complexities you’ve encountered so far are the primary ones you’ll deal with in this book. Other time complexities do exist but are far less common and tackle more complex problems. These time complexities include:

Improving Algorithm Performance

Suppose you wrote the following code that finds the sum of numbers from 1 to n.

int sumFromOneTo(int n) {
  var sum = 0;
  for (var i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

sumFromOneTo(10000);

final start = DateTime.now();
final sum = sumFromOneTo(10000);
final end = DateTime.now();
final time = end.difference(start);
print(sum);
print(time);

int betterSumFromOneTo(int n) {
  return n * (n + 1) ~/ 2;
}

Space Complexity

The time complexity of an algorithm can help predict scalability, but it isn’t the only metric. Space complexity is a measure of the memory required for an algorithm to run.

int multiply(int a, int b) {
  return a * b;
}

List<String> fillList(int length) {
  return List.filled(length, 'a');
}

List<String> stuffList(int length) {
  return List.filled(length, 'a' * length);
}

Other Notations

So far, you’ve evaluated algorithms using Big O notation, which tells the worst-case runtime. This is by far the most common measurement that programmers evaluate with. However, other notations exist as well:

Key Points

  • Time complexity is a measure of the time required to run an algorithm as the input size increases.
  • You should know about constant time, logarithmic time, linear time, quadratic time and quasilinear time and be able to order them by cost.
  • Space complexity is a measure of the memory required for the algorithm to run.
  • Big O notation represents the general form of time and space complexity.
  • Time and space complexity are high-level measures of scalability. They don’t measure the actual speed of the algorithm itself.
  • For small data sets, time complexity is usually irrelevant. A quasilinear algorithm can be slower than a quadratic algorithm.
1. Why Learn Data Structures & Algorithms?
3. Core Data Structures in Dart
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now