DSA Part 1: Time Complexity

DSA Part 1: Time Complexity

·

3 min read

Time Complexity is used to analyze the efficiency of the algorithm/problem you have used.

In short, its something on how much time it took to solve a problem. so what does it mean here?

Let say there are 10 shops in-front of you and only one shop has a Virat Kohli cricket posture. Now how will you find it ?

Virat-Kohli-PTI.jpeg

Many ideas will be crossing your mind, lets go one by one

Idea 1: First you go to shop number 1 and ask if he has VK posture, if not you ask him whether the remaining 9 shops has the VK posture? This you repeat it until you get VK posture. So here, you not only ask him but also gets info of others. This comes under order o(npower(2))

Programming level Problem: If you have two for loops with both loops searching until n, it comes under the order o(npower(2))

Idea 2: You just go and ask to every shop whether its available or not, the should be the only question. Here, you don't bother whether others has VK posture or not, this is a straight approach) This comes under order o(n)

Programming level Problem: If there are 20 balls, you need to find which ball is heavier, so you lift everything one by one so as balls increases, n also increases, this is o(n)

Idea 3: The easiest way of all I take out a speaker, I go and stand in the middle of all shops, 5 right side and 5 left, now using my speaker, I shout "whether Virat pic is on left side or right side".

If right, I reject left and repeat the approach. This comes under o(logn)

Programming level Problem: The most known problem, finding the Fibonacci series but here you are not using all the available data as explained in previous example, this comes under o(logn)

Idea 4: I take the speaker, i stand somewhere and here what i do is I ask the question loudly, "Who has Virat Kohli posture" One person responds, now you go straightaway and gets the result. This comes under order o(1)

Programming level Problem: My favorite of all, you are just finding whether the number is odd or even Smiling face with open mouth and cold sweat

A function which has number % 2 -> it gives yes or no, so this comes under order o(1)

See, now there are three different approach to every problems and the time taken completely varies from one to another and work load also varies, our energy invested also varies.

This goes same with problem solving -> the time, memory and so on varies, that's what is calculated in Time Complexity for a better efficiency and that is why Data Structures and Algorithms is used.