How does a nested if statement affect actual runtime before f(n) simplifies to O(g(n))?
I am aware that constant coefficients and constants are simply ignored when calculating runtime complexity of an algorithm. However, I would still like to know whether an if statement nested in a while or for loop adds to the total actual runtime of an algorithm, f(n).
This picture is from an intro to theoretical computer science lecture I am currently studying, and the algorithm in question counts the number of 'a's for any input string. The lecturer counts the nested if statement as one of the timesteps that affect total runtime, but I am unsure whether this is correct. I am aware that the entire algorithm simplifies to O(g(n)) where g(n) = n, but I would like to know definitively whether f(n) itself equals to 2n + a or n + a. Understanding this is important to me, since I believe first knowing exactly the actual runtime, f(n), before simplifying it to O(g(n)) reduces mistakes when calculating runtime for more complicated algorithms. I would appreciate your insight.
Youtube clip: https://www.youtube.com/watch?v=5Bbxqv73EbU&list=PLAwxTw4SYaPl4bx7Pck4JWjy1WVbrDx0U&index=35
Knowing the actual runtime, as you say, before calculating the time complexity in big-O is not important. In fact, as you continue studying, you will find that in many cases it is ambiguous, annoying or very, very difficult to find an exact number of steps that an algorithm will execute. It often comes down to definition, and depending on how you see things, you can come up with different answers.
Time complexity, on the other hand, is a useful and often easier expression to find. I believe this is the very point this video is trying to make. But to answer your question: Yes, in this case, the if statement is definitely a step that the algorithm has to make. It only compares one character, so it is clearly a constant-time operation. The author considers this comparison to take 1 step. And since it will execute n times, the total number of steps that this line of "code" will be executed is n. So yes you can see the whole algorithm as taking 2n + a steps.
However, what if we are working on a computer where we can't just compare a character in a single step, but we need to copy the character variable to a special register first, and then do the comparison. Perhaps on this computer we need to see that line as taking 2 steps, so 2n in total. Then the overall number of steps will be 3n + a, yet the time complexity is still O(n). When we study complexity theory, we don't want to go down on that level of counting, because just different ways of counting will give you different results.
You will soon learn to automatically filter out the constants and terms and identify the variables that contribute to the time complexity. When you study different algorithms, you find that as the input grows, those differences become negligible.