O(3^n) exponential time complexity [closed]

by

To be honest, if you feel like showing the guys teaching your course that their problem statement probably isn’t what they intended, I would just do it this way:

for(int i = 0; i < c; i++) { /*your code here*/}

This is in O(c), and since O(c) is a strict subset of O(ck) for k > 1, it’s also in O(ck). That’s probably not what the people teaching your course intended, they probably want you to write a loop that runs in Θ(ck).

On another note:

ck and 3n are not the same thing. Assuming the length of your input is n, ck is constant time while 3n is exponential time. Assuming the length of your input is c, ck is polynomial while 3n is constant. Assuming the length of your input is k, ck is exponential while 3n is constant.

More Related Contents:

  1. Deciding a Big-O notation for an algorithm
  2. Showing the order of growth of the function
  3. How to merge two sorted arrays into a sorted array? [closed]
  4. Is a Java hashmap search really O(1)?
  5. Stack with find-min/find-max more efficient than O(n)?
  6. What is the complexity of this simple piece of code?
  7. Example of O(n!)?
  8. Time complexity of System.arraycopy(…)?
  9. Random Number Algorithm – Implementation in Java
  10. Graph theory puzzle about connectivity?
  11. Write a program that takes an array/arraylist of integer and finds longest sub array/arraylist whose entries are equal [closed]
  12. How to check if an integer is in a set of given ranges? [closed]
  13. Generate all combinations from multiple lists
  14. Where do I find a standard Trie based map implementation in Java? [closed]
  15. Efficient swapping of elements of an array in Java
  16. Take n random elements from a List?
  17. Java, Shifting Elements in an Array
  18. Time complexity of Java’s substring()
  19. java indexof(String str) method complexity [duplicate]
  20. A better algorithm to find the next palindrome of a number string
  21. Anagram algorithm in java
  22. Nice Label Algorithm for Charts with minimum ticks
  23. Hash Set and Array List performances
  24. implementing debounce in Java
  25. How do I get the intersection between two arrays as a new array?
  26. Maximum single-sell profit
  27. How to find the only number in an array that doesn’t occur twice [duplicate]
  28. ‘MergeSort Algorithm’ – What’s the better implementation in JAVA? [closed]
  29. The simplest algorithm for poker hand evaluation
  30. How does the Euclidean Algorithm work?

Leave a Comment