Algorithms | Time and Space Analysis | Time complexity Analysis of iterative programs | RBR
Why Stack Overflow recommends it
Stack Overflow users link it when they are stuck on how to count loop iterations or derive a running time, and when they cite its examples in their own complexity questions.
Recommended by 1 people across 1 different months, 2017 to 2022.
What it is
A 37-minute algorithms lecture by Prof. Ravindrababu Ravula (RBR) on analysing the time complexity of iterative programs. It works through loop examples such as nested loops and loops with growing counters, counting how many times each line runs.
What people said
Recommends user7520940 · 2019-02 · Stack Overflow · on “Find the running time of an algorithm”
I was watching a youtube video on Time Complexity Analysis of Iterative Programs: [this video] And I cannot figure out how he calculated what's happening to line 5. The answer is k(k+1)/2. Just wondering is there certain steps I can follow or ways of thinking to figure this formula out. I know that s is the sum of the previous numbers of i. For example, i = 1, 2. Then s = 3. Or if i= 1, 2, 3, then s= 6. But I just don't know how to make up a formula for this on my own. A(){ i=1; //1 s=1; //2 while(s<=n){ //3 Value of n could be any positive integer. i++; //4 s=s+i; //5 print("hello"); //6 } }
Cites Subhi Ayman · 2017-02 · Stack Overflow · on “How this iterative function is O(n/2) when I calculate it and gives me O(n^3)”
I have this function void A() { for(int i=n/2;i<=n;i++) printf("XXX"); } and I tried to compute it's complexity with the following logic (but I know it's wrong and the correct value is O(n/2) according to tutorial 24:30 [this video] ): i value initially starts with i= n/2; then i=(n/2)+1; then i=(n/2)+2; >>>> i=(n/2)+n. This will lead to total number of execution n/2*(1 +2 +3 +4 + ....+ n) which will be n^2 definition, therefore it will have a value of O(n^3).
Cites noob anomaly · 2022-11 · Stack Overflow · on “Is this python code iterative or recursive?”
I have written the following program in python: def summ(a,b): return summation(a,a,a,b) def summation(v,c,a,b): if (c == b): return v else: return summation(v+c+1,c+1,a,b) Research on types of algorithms I am new to algorithms and programming in general and I wrote this code thinking it was an iterative algorithm but according to the following video: Algorithms lecture 2 -- Time complexity Analysis of iterative programs - YouTube [this video] iterative algorithms use loops such as 'while', 'for' recursive algorithms contain 'if .. then' statements How can I figure out whether this is an iterative or a recursive algorithm?