1.5.1 Time Complexity #1
Why Stack Overflow recommends it
Stack Overflow users link it when they need a beginner-level walkthrough of loop analysis, especially the nested loop and O(sqrt n) examples, and cite specific timestamps while asking about them.
Recommended by 1 people across 1 different months, 2019 to 2020.
What it is
A short tutorial by Abdul Bari on finding the time complexity of different code snippets, working through simple loops, nested loops and a loop whose counter grows until a running sum passes n. It builds the analysis by counting how many times statements execute.
What people said
Recommends qqq · 2020-05 · Stack Overflow · on “When can an algorithm have square root(n) time complexity?”
This link provides a very basic beginner understanding of O( ) i.e., O(sqrt n) time complexity. It is the last example in the video, but I would suggest that you watch the whole video. [this video] The simplest example of an O( ) i.e., O(sqrt n) time complexity algorithm in the video is: p = 0; for(i = 1; p <= n; i++) { p = p + i; } Mr. Abdul Bari is reknowned for his simple explanations of data structures and algorithms.
Cites Jake Cannon · 2019-02 · Stack Overflow · on “What is a more formal complexity of O(n/2)?”
I need to know how to analyze algorithms from the perspective of a discrete math class. This is not homework, the example is from here at 1:54 [this video] . Meaning, I need to to know the constants, not just the general big-0. This is the method or algorithm I'm confused with. Would It not be 3n/2 + 1 . My thought is that for the first method the for loop runs n(1/2) + 1 times and inside the for loop the statement is run n times, or maybe O(1/2) times inside as well. Then, add these two. For the subsequent method, the loop executes n + 1 times and n inside. So I believe it would be (n + 1) + n . So, 2n + 1 . This is the process I'm following for the first method but I'm not quite as confident. f
Cites Spindoctor · 2019-05 · Stack Overflow · on “Sqrt(n) time complexity”
I am new to time complexities and asymptotic notation. I was looking at this video: [this video] to figure out the time complexity of a piece of code shown below The code concludes that the time complexity for the code below is O(Sqrt(n)); When I supply different n values, I am expecting Sqrt(n) # of outputs but this doesn't verify the O(Sqrt(n)) analysis. Can someone please explain why it is so? For example if I have n = 10, I am expecting Sqrt(10) outputs which is ~ 3 outputs or 4 if you round up I guess. IS this illogical? Thanks in advance. p = 0; for( int i = 0; p <= n; i++){ p = p + i; System.out.println(p); }
Cites David · 2020-04 · Stack Overflow · on “How to calculate the time complexity for a nested loop where the second limit has the limit at the variable of the first loop”
I have a question on a specific nested loop that I found on a video ( [this video] minute : 2:45 ) So, this is the nested loop for(i = 0 ; i < n ; i++){ for(j = 0 ; j < i ; j++){ Code; // Takes in constant time (1) } } So I took n for example 5. So, if n = 5 then : i = 0 => j doesn't execute at all ( 0 times executed ) i = 1 => j = 0 ( 1 time executed ) i = 2 => j = 0 ; 1 ( 2 times executed ) i = 3 => j = 0 ; 1 ; 2 ( 3 times executed ) i = 4 => j = 0 ; 1 ; 2 ; 3 ( 4 times executed ) i = 5 => j = 0 ; 1 ; 2 ; 3 ; 4 ( 5 times executed ) So, i repeats n times , and if we look at j, it repeats 0 + 1 + 2 + 3 + 4 + 5 times, which is 0 + 1 + 2 + 3 + 4 + ... n times, so if we use the Gauss Formula j repea