Welcome to the lesson! Today, our journey will lead us through the captivating world of Complexity Analysis and techniques for optimization. These fundamental concepts are crucial for every programmer, especially those seeking to build efficient and scalable programs. Having a firm understanding of how code affects system resources enables us to optimize it for better performance. Isn't it fascinating how we can tailor our code to be more efficient? So, buckle up, and let's get started!

Now that we have refreshed our understanding of complexity analysis, let's delve into some basic examples of optimization. Optimization involves tweaking your code to make it more efficient by improving its runtime or reducing the space it uses.

An easy example of optimization could be replacing iterative statements (like a for loop) with built-in functions or using simple mathematical formulas whenever possible. Consider two functions, each returning the sum of numbers from 1 to an input number n.

The first one uses a for loop:

fun sumNumbers(n: Int): Long {
    var total: Long = 0
    for (i in 1..n) {
        total += i
    }
    return total
}

fun main() {
    val result = sumNumbers(1000000)
    println("Sum: $result")
}

The second one uses a simple mathematical formula:

fun sumNumbers(n: Int): Long {
    return n.toLong() * (n + 1) / 2
}

fun main() {
    val result = sumNumbers(1000000)
    println("Sum: $result")
}

While both functions yield the same result, the second one is much more efficient. It doesn't need to iterate through all the numbers from 1 to n. This is a classic example of optimization, where we've reimagined our approach to solving a problem in a way that uses fewer resources.

Note that although all the values between 1 and n are of type Int, we must consider that the result of the operations can exceed the limits of the Int type. Therefore, we perform conversions to Long.