|NU Year||Set: 2.(a) Marks: 4 Year: 2008|
Time complexity is a concept in computer science that deals with the quantification of the amount of time taken by a set of code or algorithm to processor run as a function of the amount of input.
In other words, time complexity is essentially efficiency, or how long a program function takes to process a given input.
Imagine a classroom of 100 students in which you gave your pen to one person. Now, you want that pen. Here are some ways to find the pen and what the O order is.
O(n2): You go and ask the first person of the class, if he has the pen. Also, you ask this person about other 99 people in the classroom if they have that pen & So on,
This is what we call O(n2).
O(n): Going and asking each student individually is O(N).
O(log n): Now I divide the class in two groups, then ask: “Is it on the left side, or the right side of the classroom?” Then I take that group and divide it into two and ask again, and so on. Repeat the process till you are left with one student who has your pen. This is what you mean by O(log n).