educative.io

Can somebody explain the calculation of Time Complexity in better words?

Courses
,
#1

Thank you in advance.

1 Like
#2

We denote time complexity by Big O notation.

For example O(n) means the program’s run time depends on the input size n.

Time complexity doesn’t mean the exact run time, but it tells you the dependency of runtime on the input size.

For example, let’s look at the following program

for (int i = 0; i <= n; i++) {
int a = 7, b = 8;
printf("%d", a + b);
}

Here, the instructions inside for loop takes constant time because this calculation is not dependent on n. No matter the size of n is smaller or larger there are only 2 instructions so it will take constant time.

But the for loop itself is dependent on n. So time complexity will be O(n).

But let’s consider the following example where for each run of first loop the inner loop will be run n times.

for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
int a = 7, b = 8;
printf("%d", a + b);
}
}
So here the complexity will be O(n^2). Hope it helps.

#3

https://www.youtube.com/playlist?list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O, learn from these. clear and easy to understand.

#4

Thank you very much for the reply.
But I actually wanted to understand the calculation of Time Complexity particular to this problem - “Happy Number”… How they reached O(log N) for the algorithm they proposed ?
I understand the mathematical term 9(square) = 81.
But the Wikipedia link is not easy to understand the sequences in this problem.

1 Like
#5

so based on his first rule.for N< 1000, it takes 1000+1 steps… okay sure. assume that is true.
then he goes on talking about N > 1000, the next number is going to be at most 81 * m. assume you have M = 3, which is three digits, the max next number is going to be 243. so if 243< 1000. then it would take at most 1001 steps.

1000/81 => 12. so up to M => 12 this log relationship would hold… so if this relationship holds up with log(N) up to N of 10e12. it means if you have even larger number. their sum of each digits square is going to be smaller than the actual number and follow the log rule based on prev logic. so overall log(n) holds still. and of course assume, the rule for N< 1000, it takes 1000+1 steps hold true.

1 Like