Difference in syntax and time complexity for C# for loop

Related searches

I am trying to figure out what the difference between the following for loops is.

The first is code that I wrote while practicing algorithms on codewars.com. It times out when attempting the larger test cases.

The second is one of the top solutions. It seems functionally similar (obviously its more concise) but runs much faster and does not time out. Can anyone explain to me what the difference is? Also, the return statement in the second snippet is confusing to me. What exactly does this syntax mean? Maybe this is where it is more efficient.

public static long findNb(long m)
{
    int sum = 0; 
    int x = new int();
    for (int n = 0; sum < m; n++)
    {
        sum += n*n*n;
        x = n;
        System.Console.WriteLine(x);
    }
    if (sum == m)
    {
        return x;
    }
    return -1;
}

vs

public static long findNb(long m) //seems similar but doesnt time out
{
    long total = 1, i = 2;
    for(; total < m; i++) total += i * i * i;
    return total == m ? i - 1 : -1;
}

The second approach uses long for the total value. Chances are that you're using an m value that's high enough to exceed the number of values representable by int. So your math overflows and the n value becomes a negative number. You get caught in an infinite loop, where n can never get as big as m.

And, like everyone else says, get rid of the WriteLine.

Also, the return statement in the second snippet is confusing to me. What exactly does this syntax mean?

It's a ternary conditional operator.

Loops in C#, Pseudo-polynomial Algorithms � Polynomial Time Approximation Scheme � A Time Complexity Syntax: while (boolean condition) { loop statements } Flowchart: while loop but with different syntax. for loops are preferred when the executing the statements, i.e it will execute the loop body one time for� A for loop is a repetition control structure that allows you to efficiently write a loop that needs to execute a specific number of times. Syntax. The syntax of a for loop in C# is − for ( init; condition; increment ) { statement(s); } Here is the flow of control in a for loop − The init step is executed first, and only once. This step

Both approaches are roughly the same, except unwanted System.Console.WriteLine(x); which spolis the fun: printing on the Console (UI!) is a slow operation.

If you are looking for a fast solution (esp. for the large m and long loop) you can just precompute all (77936) values:

 public class Solver {
   static Dictionary<long, long> s_Sums = new Dictionary<long, long>();

   private static void Build() {
     long total = 0;

     for (long i = 0; i <= 77936; ++i) {
       total += i * i * i;

       s_Sums.Add(total, i);
     }
   } 

   static Solver() 
     Build(); 
   }

   public static long findNb(long m) {
     return s_Sums.TryGetValue(m, out long result) 
       ? result 
       : -1;
   }
 }

C#, Pseudo-polynomial Algorithms � Polynomial Time Approximation Scheme � A Time Complexity Question The foreach loop is used to iterate over the elements of the collection. Syntax: foreach(data_type var_name in collection_variable) { // statements to Difference between for loop and foreach loop:. C# For Loop: Iteration 1 C# For Loop: Iteration 2 C# For Loop: Iteration 3 C# For Loop: Iteration 4 C# For Loop: Iteration 5. In this example, we haven't used the initialization and iterator statement. The variable i is initialized above the for loop and its value is incremented inside the body of loop. This program is same as the one in Example 1.

When I run into micro optimisation challenges like this, I always use BenchmarkDotnet. It's the tool to use to get all the insights to performance, memory allocations, deviations in .NET Framework versions, 64bit vs 32 bit etc. etc.

But as others write - remember to remove the WriteLine() statement :)

Reducing Nested Loop Complexity, I think writing algorithms in Big O syntax comes naturally. I mean I In this example I'm using C Duration: 7:11 Posted: Oct 31, 2018 Time complexity of if-else statements in a for loop Tag: if-statement , for-loop , time-complexity , asymptotic-complexity Let A[1, …, n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is θ(m).

Introduction to Programming with C# / Java Books � Chapter 19 , In this chapter we will compare the data structures we have learned so far by the and Duration: 1:37:41 Posted: Jul 31, 2012 May it be a for loop or a while loop, if there is only one statement in the body of the loop, the curly braces are not required in that condition. Key Differences Between for and while loop In for loop, initialization, condition checking, and increment or decrement of iteration variable is done explicitly in the syntax of a loop only.

Complexity and Big-O Notation, Other methods may perform different numbers of operations, depending on the value of a When we consider the complexity of a method, we don't really care about the exact Note that, for a given N, the for-loop above is equivalent to:. For any loop, time complexity depends on the number of iterations and the statements inside the body of the loop. For simplicity, we assume that the loop body is O (1), so that we could now look into only the iterations part of it. The iterations could be a fixed number or vary depending on some value. If it is fixed, the time complexity is O (1).

Note: In Exit Controlled Loops, loop body will be evaluated for at-least one time as the testing condition is present at the end of loop body. 1. do-while loop do while loop is similar to while loop with the only difference that it checks the condition after executing the statements, i.e it will execute the loop body one time for sure because

Comments
  • Could be that System.Console.Writeline call. That's a lot of work for such a tight loop.
  • Try it with and without the Writeline
  • total == m ? i - 1 : -1 is called a ternary operator. If the condition total == m is true then i - 1 is evaluated, otherwise -1. The evaluated expression is then returned
  • Without knowing the value of m it's difficult to say, but I'd agree that it's most likely the Console.Writeline calls.
  • remove the console write line and x then your code is equivalent to the other one. You can keep one or the other to figure out what makes your code slow; I do agree with the previous comments that console write line is most likely the issue.
  • int vs long was the problem. the test was trying some trillion or quadrillion order of mag that was too big for int. Thanks!
  • Thanks for all the reply. Console.Writeline was actually excluded from the code when it ran. For some reason even without Console.Writeline, it is still timing out.