finding the correct time complexity of these codes
NickName:mas Ask DateTime:2020-10-10T23:30:54

finding the correct time complexity of these codes

I was trying to find time complexity of these 2 codes but i am not sure about my answers .

code1

   int i = 1;
    int count = 0;
   
    while (i < n) {

        for (int j = 0; j < i; j++) {
            count++;
        }
        i *= 2;
    }

I calculated the number of steps in loops and I reached to (log n)^2 but i am not sure about it .

Code2

int k=0;
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                k++;
                break;
            }
        }

    }

and for this one I got ( n * log n)

actually I am new to calculating time complexity and I am not sure about them , could you help me find the correct answer .

Copyright Notice:Content Author:「mas」,Reproduced under the CC 4.0 BY-SA copyright license with a link to the original source and this disclaimer.
Link to original article:https://stackoverflow.com/questions/64295148/finding-the-correct-time-complexity-of-these-codes

More about “finding the correct time complexity of these codes” related questions

finding the correct time complexity of these codes

I was trying to find time complexity of these 2 codes but i am not sure about my answers . code1 int i = 1; int count = 0; while (i &lt; n) { for (int j = 0; j &lt; i; j++) ...

Show Detail

Comments in codes increase time complexity of a program?

Do Comments in code increase time complexity of a program.? I have many running applications wherein there are codes which are commented within functions. These commented codes are of 500 lines w...

Show Detail

Time and space complexity of these codes

I just learned about time and space complexity and I dont think I am really grasping them. I will put up some codes would would ask kindly if some of you could tell me their time and space complexi...

Show Detail

What is the Time Complexity and Space complexity of the following codes?

Here are the codes attached below. I have done these problems in one of the FAANG companies. I am open to have a discussion on time complexity and space complexity of these codes. Code1: public sta...

Show Detail

Finding Time and Space Complexity Of Recursive Functions

I am stumbling at anlayzing the time and space complexities of recursive functions: consider: def power(a, n): if n==0: return 1 else: return a*power(a, n-1) When finding...

Show Detail

Time Complexity for Finding the Minimum Value of a Binary Tree

I wrote a recursive function for finding the min value of a binary tree (assume that it is not ordered). The code is as below. //assume node values are positive int. int minValue (Node n) { if(n ==

Show Detail

Finding the time complexity of a recursive algorithm

I was solving a few problems related to finding the time complexity of algorithms and came across this question. It gave me a real hard time figuring what could possibly be the time complexity of t...

Show Detail

Finding time complexity of a program

I'm solving the following programming question: Given a sorted integer array and a number, find the start and end indexes of the number in the array. Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Nu...

Show Detail

Time complexity for finding the nth prime number

How can I find the time complexity for my code below: if (nprime == 1) return 2; if (nprime == 2) return 3; int count = 3; int primeNum = -1; for (int i = 5; count &lt;= npr...

Show Detail

finding the time complexity

I am trying to understand the subtle difference in the complexity of each of the examples below. Example A int sum = 0; for (int i = 1; i &lt; N; i *= 2) for (int j = 0; j &lt; N; j++) ...

Show Detail