Time Complexities

Question

So I recently came across an interview question on codewars, it goes thus:
A list of of 1 to 100 with one number removed is provided and your task is to find the number and the the time complexity (optional).

Solutions might be:
-> 5050 - sum([list])
-> [n for n in range(1,101) if n not in list][0]
-> sum(range(101)) - sum(list)
etc.

My question is this: how do you discern or tell the time complexity of each solution?

# If you know a good book on algorithm and time complexities, please recommend 🙏🙏 as fast algorithms make for efficient codes

Answer 1

the time complexity is linear because you have to traverse through each element in the array at least once

there is no faster way because you have to find out what numbers you already have

all the solutions you listed run in linear time.

for books try “Introduction to Algorithms” by CLRS

edit:
I also wrote a tutorial about complexity analysis here:

https://code.sololearn.com/cAAmIcha1GsN/?ref=app

Answer 2

Tomiwa Joseph
Most of the competetive programming and interviews technical coding entrance problems sets is giving some constraints according to which you need to devlope your logic..

Time complexity of each solution is based over the used approach in the code. Brute force approach is the one in which the time complexity is comparatively much higher than the one required as used of nested for loops in solution with all unnecessary elements traversal.

Optimal approach is the one in which we tried to reduce the code with using many type of algorithms like divide and conquer technique, dynamic programming, memory memorization etc.

Some solutions which include recursion too time out in online platform due to recursion limit exceed which need to be solved with reducing the code and using different algorithms for different problems.

Here is an lesson regarding the "Time Complexity" have an read.

For algorithm books as suggested by Bobby(Corman) is best one .
https://www.sololearn.com/learn/6362/?ref=app