Scribd Logo
Upload

Welcome to Scribd!

  • 61 views

    Q1) O (1) Time Complexity in Loops:: // Here C Is A Constant

    Uploaded by

    Avirup Ray
    Loops with a constant number of iterations or that increment/decrement the counter by a constant amount at each step have O(1) or O(n) time complexity, respectively. Nested loops have complexity equal to the number of times the innermost statement executes, like O(n^2) for a double loop. A loop that multiplies/divides the counter by a constant each iteration has O(logn) complexity, while one that increases/decreases the counter exponentially has O(loglogn) complexity. When multiple loops are consecutive, their complexities are added to find the overall complexity, like O(m+n) for loops of sizes m and n running consecutively.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Q1) O (1) Time Complexity in Loops:: // Here C Is A Constant

    Uploaded by

    Avirup Ray
    61 views2 pages
    Loops with a constant number of iterations or that increment/decrement the counter by a constant amount at each step have O(1) or O(n) time complexity, respectively. Nested loops have complexity equal to the number of times the innermost statement executes, like O(n^2) for a double loop. A loop that multiplies/divides the counter by a constant each iteration has O(logn) complexity, while one that increases/decreases the counter exponentially has O(loglogn) complexity. When multiple loops are consecutive, their complexities are added to find the overall complexity, like O(m+n) for loops of sizes m and n running consecutively.

    Original Title

    Sorting,Searching

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Loops with a constant number of iterations or that increment/decrement the counter by a constant amount at each step have O(1) or O(n) time complexity, respectively. Nested loops have complexity equal to the number of times the innermost statement executes, like O(n^2) for a double loop. A loop that multiplies/divides the counter by a constant each iteration has O(logn) complexity, while one that increases/decreases the counter exponentially has O(loglogn) complexity. When multiple loops are consecutive, their complexities are added to find the overall complexity, like O(m+n) for loops of sizes m and n running consecutively.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    61 views2 pages

    Q1) O (1) Time Complexity in Loops:: // Here C Is A Constant

    Uploaded by

    Avirup Ray
    Loops with a constant number of iterations or that increment/decrement the counter by a constant amount at each step have O(1) or O(n) time complexity, respectively. Nested loops have complexity equal to the number of times the innermost statement executes, like O(n^2) for a double loop. A loop that multiplies/divides the counter by a constant each iteration has O(logn) complexity, while one that increases/decreases the counter exponentially has O(loglogn) complexity. When multiple loops are consecutive, their complexities are added to find the overall complexity, like O(m+n) for loops of sizes m and n running consecutively.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 2

    Q1) O(1) Time complexity in loops: 

    Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop,
    recursion and call to any other non-constant time function.
    A loop or recursion that runs a constant number of times is also considered as O(1). For example the
    following loop is O(1).

    for (int i = 1; i <= c; i++) // Here c is a constant


    {
    // some O(1) expressions
    }
    Q2) O(n) Time Complexity in loops: 
    Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a
    constant amount.

    for (int i = 1; i <= n; i += c)// Here c is a positive integer constant


    {
    // some O(1) expressions
    }

    for (int i = n; i > 0; i -= c)


    {
    // some O(1) expressions
    }

    Q3) O(nc) complexity in loops: Time complexity of nested loops is equal to the number of times the
    innermost statement is executed. For example the following sample loops have O(n 2) time complexity

    for (int i = 1; i <=n; i += c) {


    for (int j = 1; j <=n; j += c) {
    // some O(1) expressions
    }
    }

    for (int i = n; i > 0; i -= c) {


    for (int j = i+1; j <=n; j += c) {
    // some O(1) expressions
    }

    Q4) O(Logn) Time complexity in loops


    Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a
    constant amount.
    for (int i = 1; i <=n; i *= c)
    {
    // some O(1) expressions
    }

    for (int i = n; i > 0; i /= c)


    {
    // some O(1) expressions
    }
    .
    Q5) O(log(logn)) Time complexity in loops
    Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased
    exponentially by a constant amount.

    for (int i = 2; i <=n; i = pow(i, c)) //Here c is a constant greater than 1


    {
    // some O(1) expressions
    }

    for (int i = n; i > 1; i = fun(i))//fun(i)=square root ,cube root,4th root…….of i


    {
    // some O(1) expressions
    }

    Q6) How to combine time complexities of consecutive loops?


    When there are consecutive loops, we calculate time complexity as sum of time complexities of
    individual loops.
    for (int i = 1; i <=m; i += c)
    {
    // some O(1) expressions
    }

    for (int i = 1; i <=n; i += c)


    {
    // some O(1) expressions
    }
    Time complexity of above code is O(m) + O(n) => O(m+n)
    If m == n, the time complexity becomes O(2n) which is O(n).

    You might also like