DS Algorithm Analysis: Exercises

Section 2.10 Algorithm Analysis: Exercises

Here are exercises to practice your understanding.

Give the Big O performance of the following code fragment:

for (i in 0 ..< n) {
    for (j in 0 ..< n) {
        val k = i + j
    }
}

Give the Big O performance of the following code fragment:

for (i in 0 ..< n) {
    val k = 2 * i
}

Give the Big O performance of the following code fragment:

var i = n
while (i > 0) {
    val k = 2 * i
    i = i / 2
}

Give the Big O performance of the following code fragment:

var result = 0
for (i in 0 ..< n) {
   for (j in 0 ..< n) {
      for (k in 0 ..< n) {
         result = i + j + k
      }
   }
 }

Give the Big O performance of the following code fragment:

var result = 0
for (i in 0 ..< n) {
   result = i + i
}
for (j in 0 ..< n) {
   result = j + j
}
for (k in 0 ..< n) {
   result = k + k
}

Devise an experiment to verify that the Kotlin list indexOf operation is \(O(n)\text{.}\)

Devise an experiment to verify that get and put are \(O(1)\) for Kotlin maps.

Devise an experiment that compares the performance of the remove operation function on lists and maps.

Given a list of numbers in random order, write an algorithm that works in \(O(n\log(n))\) to find the \(k\text{th}\) smallest number in the list.

Can you improve the algorithm from the previous problem to be linear? Explain.

You have attempted of activities on this page.