Introduction

In the previous section, we already discuss Constant Time in Big O Notation, now I am gonna show you what is Linear Time in Big O Notation.

Okay lets go into the coding section:

fun main() {
    var listOfItem = arrayListOf<String>("plate","glass","spoon")
    var targetValue = "glass" 
    println(findTheItem(listOfItem, targetValue))
}

fun findTheItem(item: ArrayList<String>, targetValue: String)
: Boolean {

    for (i in 0 until item.size){
        println("current index is ${i} times")
        if(item[i] == targetValue) return true
    }
    return false
}

Okay before discussing Linear time, I want to tell you what the code's purpose is. You can see in the findTheItem function we want to find the elements of the array that contains the value that we were looking for.

How about figuring out the time complexity of it?

The simple way to find out the complexity line by line:

We are going to be looking through= this function and look at all the steps necessary for finding whether the "targetValue" was found or not:

fun findTheItem(item: ArrayList<String>, targetValue: String)
: Boolean {

    for (i in 0 until item.size){
        println("current index is ${i} times")
        if(item[i] == targetValue) return true
    }
    return false
}

So this case here, the first operation that happens is in this function is that we were setting the looping using form 0 until the last index of array that we input.

for (i in 0 until item.size){
        println("current index is ${i} times")
        if(item[i] == targetValue) return true
    }

This is where things started to happen because this is the for loop, which means everything inside the function will execute as much as the array we input because we set the looing until the end of the index of elements, or in a simple way we can say it n times, n times means that the number of operation executed is never defined in the first time.

If our input of the array is 9 elements, that is mean the looping will run through for the looping with the worst scenario at 9 times or until we get the target we want. If there is no target equal to the element of the array then we return the false value. Now we can understand because our loop is dependent on the input of the array, then the Big O of the looping is Big O (n). now how about the last instruction after all the loops we can not find the equal value of the "targetValue"? then we have to return false.

return false

If we see at the code, return false is just executed once the Big O is Big O (1).

1. The Looping will execute at least n times worst-case scenario

2. The biggest the array we input, the longer the operation