You are not logged in. Please login at www.codechef.com to post your questions!

×

Find Nth term of any Linear Recurrence Relation in O(logN) complexity.

asked 10 Jul '18, 19:08

cenation092's gravatar image

5★cenation092
18711
accept rate: 6%

edited 10 Jul '18, 19:10

Is matrix multiplication O(1) ?

(18 Jul '18, 23:16) shashwat0014★

yes @shashwat001
O(1) means constant time... each matrix multiplication (given that both matrix have same dimension) will take constant time (a fixed amount of computations which won't depend on any other factor like n,k ) ...

(18 Jul '18, 23:58) l_returns5★
1

matrix multiplication will be O(k^3). (Its better than using the divide and conquer approach which has high constant factor).

(19 Jul '18, 09:35) soham12346★
1

agree... where k is dimension of matrix right ?

(19 Jul '18, 14:11) l_returns5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×348
×137
×116

question asked: 10 Jul '18, 19:08

question was seen: 193 times

last updated: 19 Jul '18, 14:11