Advertisement
Guest User

Untitled

a guest
Jun 25th, 2019
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.15 KB | None | 0 0
  1. Even or odd: Constant time O(1)
  2. function isEven(value){
  3. //determine if a value is even if remainder is 0 after division
  4. //I assume the complexity is here, at the math operation but I'm not sure.
  5. if (value % 2 == 0){
  6. //if remainder 0, return true
  7. return true;
  8. }
  9. else
  10. return false;
  11. }
  12.  
  13. Are you here: Polynomial time O(n^k) O(n^2)
  14. function areYouHere(arr1, arr2) {
  15. // Nested loops are characteristic of O(n^k) time apparently
  16. // First loop over the first array
  17. // I'm assuming that the loop is the complex part of the algorithm but i'm not sure.
  18. // I don't think that assigning variables to values would result in increased time complexity but again, i'm not sure.
  19. // If i is less than the length of array 1, increment by 1
  20. for (let i=0; i<arr1.length; i++) {
  21. // assign the value of the index in arr1 to el1
  22. const el1 = arr1[i];
  23. // Second loop(nested loop) over the second array(nested array)
  24. for (let j=0; j<arr2.length; j++) {
  25. const el2 = arr2[j];
  26. if (el1 === el2) return true;
  27. //If another loop was implemented I think that the complexity would be O(n^3) and so on.
  28. }
  29. }
  30. return false;
  31. }
  32.  
  33. Doubler: Linear time O(n) O(1)
  34. function doubleArrayValues(array) {
  35. //Loop over the input and double each index
  36. for (let i=0; i<array.length; i++) {
  37. array[i] *= 2;
  38. }
  39. return array;
  40. }
  41.  
  42. Naive Search: Constant time O(1) WRONG it's Linear time but I don't know why.
  43. function naiveSearch(array, item) {
  44. // Is the loop considered one operation? Or is each iteration considered one operation?
  45. // I'm assuming this is Constant time as it's accessing an array item.
  46. for (let i=0; i<array.length; i++) {
  47. if (array[i] === item) {
  48. return i;
  49. }
  50. }
  51. }
  52.  
  53. Creating pairs: Polynomial time O(n^2)
  54. function createPairs(arr) {
  55. //I'm guessing because I am confused. I only say Polynomial time
  56. //because of the nested loops.
  57. //Loop over first array
  58. for (let i = 0; i < arr.length; i++) {
  59. //Loop over 2nd array one index space ahead of first array(I think).
  60. //I think this will allow comparisons to be made between array elements/indices
  61. //in order to determine pairs/like elements
  62. for(let j = i+1; j < arr.length; j++) {
  63. //
  64. console.log(arr[i] + ", " + arr[j] );
  65. }
  66. }
  67. }
  68.  
  69. Computing fibonaccis: Constan time O(1) but i'm just guessing. WRONG it's Linear time O(n) which kind of makes sense to me.
  70. function generateFib(num) {
  71. let result = [];
  72. for (let i = 1; i <= num; i++) {
  73. //The comments below are taken directly from the code snippet and are not mine.
  74. // we're adding the first item
  75. // to the result list, append the
  76. // number 0 to results
  77. if (i === 1) {
  78. result.push(0);
  79. }
  80. // ...and if it's the second item
  81. // append 1
  82. else if (i == 2) {
  83. result.push(1);
  84. }
  85.  
  86. // otherwise, sum the two previous result items, and append that value to results.
  87. else {
  88. result.push(result[i - 2] + result[i - 3]);
  89. }
  90. }
  91. // once the for loop finishes
  92. // we return `result`.
  93. return result;
  94. }
  95.  
  96. An Efficient Search: Logarithmic time O(log(n))
  97. function efficientSearch(array, item) {
  98. let minIndex = 0;
  99. let maxIndex = array.length - 1;
  100. let currentIndex;
  101. let currentElement;
  102.  
  103. while (minIndex <= maxIndex) {
  104. //Return an integer that is <= the first element in the array added to the last element in the array and divide it by 2.
  105. //It appears to cut in half, the array.
  106. //currentIndex has the value of the math operation.
  107. currentIndex = Math.floor((minIndex + maxIndex) / 2);
  108. //currentElement has the value of the index position in the array, which is in the middle of the array, I think.
  109. currentElement = array[currentIndex];
  110. // This appears to be a loop. If the currentElement is less than item, increment by 1 and assign that value to minIndex.
  111. // Does this have the effect of searching the "left" side of the divided array? Or is it the "right" side?
  112. if (currentElement < item) {
  113. minIndex = currentIndex + 1;
  114. }
  115. // Does this have the effect of searching the "right" side of the array, or "left" side?
  116. else if (currentElement > item) {
  117. maxIndex = currentIndex - 1;
  118. }
  119. else {
  120. return currentIndex;
  121. }
  122. }
  123. return -1;
  124. }
  125.  
  126. Random element: Exponential time O(2^n) WRONG it's Constant time O(1)
  127. function findRandomElement(arr) {
  128. //I think this will return the product of a random number from the array times the number of elements in the array.
  129. //I'm guessing Exponential time due to the multiplication operation. Either that or Constant time. (I was close.).
  130. //I should have known because it's a simple math operation.
  131. return arr[Math.floor(Math.random() * arr.length)];
  132. }
  133.  
  134. Is it prime: Linear time O(n)
  135. function isPrime(n) {
  136. //Comments below are taken from the code snippet and are not mine.
  137. // if n is less than 2 or is a decimal, it's not prime
  138. if (n < 2 || n % 1 != 0) {
  139. return false;
  140. }
  141. // otherwise, check if `n` is divisible by any integer
  142. // between 2 and n.
  143. for (let i = 2; i < n; ++i) {
  144. if (n % i == 0) return false;
  145. }
  146. return true;
  147. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement